Description

Carmen — a Holsteins cow dearly valued by Farmer John — has fallen into a “trash well,” a place where farmers dump garbage. The well has a depth of $D$ ($2 \le D \le 100$) feet.

Carmen plans to stack trash. When the stacked trash reaches or exceeds the well’s depth (that is, the total trash height $\geq D$), she can escape. She can also eat some trash to extend her survival.

Each piece of trash can be either eaten or stacked, and stacking takes no time for Carmen.

Assume Carmen knows in advance the time $t$ ($1 \le t \le 1000$) when each piece of trash is thrown in, as well as each piece’s stacking height $h$ ($1 \le h \le 25$) and the survival time increase $f$ ($1 \le f \le 30$) if eaten. Find the earliest time when Carmen can escape. Initially, Carmen has enough energy to last 10 hours. If Carmen goes 10 hours without eating (10 hours excluded; the same applies to added survival time), she will starve. In particular, if her energy is 0 and she eats a piece of trash or escapes at that instant, she will not starve.

Input Format

The first line contains two integers, $D$ and $G$ ($1 \le G \le 100$), where $G$ is the number of pieces of trash thrown into the well.

Each of the next $G$ lines contains three integers: $t$ ($1 \le t \le 1000$), the time when the trash is thrown in; $f$ ($1 \le f \le 30$), the survival time this trash can provide if eaten; and $h$ ($1 \le h \le 25$), the height this trash can add if stacked.

Output Format

If Carmen can climb out of the trap, output a single integer, the earliest time when she can climb out. Otherwise, output how long she can survive at most.

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

13

Hint

【Sample Explanation】

Carmen stacks the first piece of trash she receives: $\mathrm{height}=9$.

Carmen eats the second piece of trash, extending her survival from 10 hours to 13 hours.

Carmen stacks the third piece of trash, $\mathrm{height}=19$.

Carmen stacks the fourth piece of trash, $\mathrm{height}=20$.

Translated by ChatGPT 5