Warehouse
Vasya, a young boy, went to the grocery store with his mom to buy a "Prague" cake. When his mom requested the cake, the seller disappeared into the next room and returned with it, much to Vasya's amazement. Intrigued by this mysterious room, Vasya convinced his mom to buy another cake. As the seller went to fetch the second cake, Vasya quietly followed him and discovered a cake warehouse filled with "Bees," "Flight," and "Kyiv" cakes. Undeterred by the variety, Vasya decided to find the tastiest cake. However, he was unaware that the warehouse was heavily guarded and that many boys before him had entered but never returned. Oblivious to the danger, Vasya began exploring the warehouse. Suddenly, he stepped on a red mark on the floor, causing the ground to collapse beneath him, and he fell into a deep pit with a depth of D feet (2 ≤ D ≤ 100). Being a pioneer, Vasya remained calm and started looking for a way out. He discovered that cakes were occasionally thrown into the pit, which he could either eat or stack to escape. To climb out, he needed to build a pile of cakes reaching a height of D. However, Vasya needed to balance his energy by eating some cakes to survive longer. From secret notes on the pit wall, Vasya learned the schedule of cake deliveries. Help Vasya escape!
Assume Vasya fell into the pit at time 0, and initially, he has enough energy for 10 hours. If Vasya has, for example, 3 hours of energy left and the next cake arrives in exactly 3 hours, he can start eating immediately and won't starve.
Input
The input begins with two integers: D, the depth of the pit, and G, the number of cakes thrown into the pit (1 ≤ G ≤ 100). Following this are the details of each cake, given as three integers: T, the time in hours when the cake will be thrown into the pit (0 < T ≤ 1000); F, the number of additional hours of life Vasya gains by eating the cake (1 ≤ F ≤ 30); and H, the height of the cake in feet (1 ≤ H ≤ 25).
Output
Output the minimum number of hours Vasya needs to escape. If escape is impossible, print the maximum number of hours he can survive.