题目描述

小牛卡门不慎跌入了一口深 $D$（$2 \le D \le 100$）英尺的废井中。井口的农夫们不断往井里扔垃圾。卡门可以选择将垃圾堆起来增加高度，也可以吃掉垃圾延长生命。

每个垃圾被扔下的时间 $t$（$1 \le t \le 1000$）、可垫高的高度 $h$（$1 \le h \le 25$）和吃下后延长的生命时间 $f$（$1 \le f \le 30$）都是已知的。卡门初始有持续 $10$ 小时的能量，若在两次进食之间间隔达到 $10$ 小时（不含 $10$ 小时），卡门就会饿死。特别地，若体力值为 $0$ 时吃下垃圾或逃出井外也不会饿死。

当堆起的垃圾总高度 $\ge D$ 时，卡门可以逃出井外。求卡门最早能逃出的时间；若无法逃出，求卡门最长能存活多长时间。

输入格式

第一行为两个整数 $D$ 和 $G$（$1 \le G \le 100$），$G$ 为投入井中的垃圾数量。

接下来 $G$ 行，每行三个整数 $t$、$f$、$h$，分别表示该垃圾的投下时间、生命延续时间和垫高高度。

输出格式

若卡门能逃出，输出最早逃出时间（一个整数）；否则输出卡门最长存活时间。

样例

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

13

提示

【样例说明】

• 堆放第 $1$ 个垃圾：高度变为 $9$；
• 吃掉第 $2$ 个垃圾：生命从 $10$ 延长到 $13$；
• 堆放第 $3$ 个垃圾：高度变为 $19$；
• 堆放第 $4$ 个垃圾：高度变为 $20 \ge 20$，在时间 $13$ 逃出。