时间限制：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\) 该食物能垫高的高度。

【输出格式】

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

【输入输出样例】

　Input

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

　Output

13

【输入输出样例解释】

　　黑仔堆放第 1 份食物：高度为 9；
　　黑仔吃掉第 2 份食物，使她的生命从 10 小时延伸到 13 小时；
　　黑仔堆放第 3 份食物，高度为 19；
　　黑仔堆放第 4 份食物，高度为 20。

【数据限制】

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

【来源】

　　Mr.he