测试数据来自 system/2114

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　狼王黑仔不幸掉入到猎人的“陷阱”中，陷阱深度为 \(d\) 米。

　　朋友双毛想要救出黑子，但首要任务是延续它的生命，黑仔体内开始有足够持续 10 小时的能量，如果 10 小时内没有进食，它将饿死。

　　于是双毛着急地到处找寻食物，并不断地把找到的食物丢入阱中。黑仔每次得到食物，它可以把食物堆起来，等到堆得大于等于陷阱高时，她就能逃出陷阱了；它也可以通过吃一些食物来维持自己的生命。每个食物都可以用来吃或堆放，并且堆放食物不用花费黑仔的时间。

　　假设给出双毛扔下食物的时间 \(t_i\)，以及每个食物堆放的高度 \(h_i\) 和吃进该食物能维持生命的时间 \(f_i\)，请你计算黑仔最早能逃出陷阱的时间。

【输入格式】

　　第 1 行为 2 个整数，\(d\) 和 \(n\)，\(d\) 为陷阱的深度，\(n\) 为被投入陷阱的食物的数量。
　　第 2 到第 \(n+1\) 行每行包括 3 个整数：\(t_i、f_i\) 和 \(h_i\)，\(t_i\) 表示第 \(i\) 份食物被投进陷阱中的时间；\(f_i\) 表示该第 \(i\) 份食物能维持黑仔生命的时间；\(h_i\) 该食物能垫高的高度。

【输出格式】

　　如果黑仔可以爬出陷阱，输出一个整表示最早什么时候可以爬出；否则输出黑仔最长可以存活多长时间。

【输入输出样例1】

　Input

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

　Output

13

【样例1解释】

　　狼王能逃出“陷阱”，具体操作如下：
　　狼王堆放第1份食物：高度为9；
　　狼王吃掉第2份食物，使她的生命从10小时延伸到13小时；
　　狼王堆放第3份食物，高度为19；
　　狼王堆放第4份食物，高度为20。
　　刚好走出“陷阱”。

【输入输出样例2】

　Input

6 5
10 30 5
40 30 5
70 30 5
100 25 5
130 2 5

　Output

125

【样例2解释】

　　本样例中，狼王无法逃出“陷阱”，但它最长能存活125小时。

【数据限制】

　　对于 \(100\%\) 的数据，\(2≤d≤100\)，\(1≤n≤100\)，\(0<t_i≤1000\)，\(1≤h_i≤25\)，\(1≤f_i≤30\)

【来源】

　　Mr.he