Survival and Escape

After slipping, you fall into a trap of depth D. Boxes containing food are thrown into the trap over time. For each box, you may choose exactly one use: eat its contents to increase your HP, or leave it unopened and stack it on the floor to raise your foothold. Once a box is emptied, it collapses if used as a foothold, so one box cannot be both eaten and stacked.

You start at time 0 with HP 10. Each unit of time decreases HP by 1. If food arrives exactly when HP reaches 0, you may eat it immediately and continue surviving. Using the given boxes, find the earliest time when the stacked height can reach at least D and you can escape.

The first line contains two natural numbers D and G. D is the depth of the trap, and G is the number of boxes thrown in.

Each of the next G lines contains three natural numbers T, F, and H describing one box. T is the time when the box is thrown in, F is the amount of HP gained by eating its contents, and H is the height gained by stacking the box. The box information may not be sorted by time.

If escape is possible, output the earliest time when you can escape. If escape is impossible, output the maximum time until which you can survive.

• 1 <= D <= 100
• 1 <= G <= 100
• 1 <= T <= 1000
• 1 <= F <= 30
• 1 <= H <= 25

One optimal choice is to stack the first box, making the height 9, and eat the second box, extending survival to time 13. Stacking the third box raises the height to 19, and stacking the fourth box raises it to 20, allowing escape. Escaping with HP exactly 0 does not mean you die.