22858_TrappedintheWe

Carmen, one of FJ's prized Holsteins, has fallen into the "garbage well".  The "garbage well" is where the farmers throw their garbage, a frequent occurrence as it turns out.  It is D (2 ≤ D ≤ 100) feet deep.

Carmen has figured out that she can escape the well if she can make a pile of garbage at least as high as the well and climb out.  Carmen has also figured out that she can eat the garbage in order to extend her life at the bottom of the well.  Each piece of garbage serves at most one purpose: eating or stacking, but not both.  Happily, stacking garbage takes no time at all.

Given a listing of garbage pieces thrown into the well, figure out the earliest time (if one exists) that Carmen can escape the well.  Carmen currently has enough energy inside her to last 10 hours and is starting this exercise at time=0.

Note that if Carmen has 10 hours of food and the next piece arrives in 10 hours of time (right when her food supply runs out), Carmen does not starve to death but can immediately start eating the next batch of food.

* Line 1: Two integers: D and G (1 ≤ G ≤ 100) (the number of pieces of garbage thrown into the well)

* Lines 2..G+1: Each line contains three integers: T (0 < T ≤ 1000), the time in hours that the garbage is thrown into the well (not necessarily unique!); F (1 ≤ F ≤ 30), the number of hours of nutrition the garbage provides as food; and H (1 ≤ H ≤ 25), the height in feet of the garbage.

A single line with the integer minimum number of hours either until Carmen escapes or, if she cannot possibly escape, the maximum hours that Carmen can survive.

20 4
5 4 9
9 3 2
12 6 10
13 1 1

13

Explanation:

* Carmen stacks the first garbage she receives: height=9.

* Carmen eats the second garbage, extending her life from 10 units to 13.

* Carmen stacks the third garbage: height=19.

* Carmen stacks the fourth garbage: height=20.  She's alive and can climb out.