Vasya came with his mother to the grocery store. They decided to buy a "Prague" cake, and his mother told the seller about it. The seller went to the next room without a cake and returned with one, which surprised Vasya—after all, he did not visit the room where cakes appeared every day. He wanted to investigate this phenomenon and convinced his mother to buy a different cake. When the seller went to get another cake, Vasya quietly followed him. What a sight he saw: he found himself in a cake warehouse. There stood the "Bees," the "Flight," and the "Kyiv" cakes... But Vasya was not overwhelmed by such abundance and decided to find the tastiest cake in the warehouse. He did not realize that cakes were under heavy guard, and that hundreds of boys had entered this warehouse before him—but none had ever returned home... Oblivious to these dangers, Vasya started exploring the warehouse, and when he accidentally stepped on a red mark on the floor, the ground gave way, and Vasya fell into a deep pit (the depth of the pit is feet, 2 \le D \le 100). Vasya was a scout and did not panic; instead, he began to look for a way out. It turned out that from time to time, cakes were thrown into this pit, and Vasya could either eat them or stack them into one large pile. Each cake could be either eaten completely or used for stacking, but not both. To climb out, Vasya must build a pile of cakes with a height of at least . At the same time, Vasya's strength is not unlimited, and to live longer in the pit, he needs food—the very cakes that he might also need to stack. By deciphering secret records on the pit wall, Vasya learned which cakes and when would be thrown down. Help Vasya escape!
Assume that Vasya fell into the pit at time , and he initially has enough strength for hours. Note that if, for example, Vasya has hours of strength left and the next cake is dropped exactly hours later, Vasya can start eating immediately and will not die of hunger.
At the beginning of the input file, the integers (the pit depth) and (the number of cakes thrown into the pit) are given (1 \le G \le 100). Then, descriptions of the cakes follow—three integers per cake: is the time in hours when the cake will be thrown into the pit (0 < T \le 1000), is the number of extra hours of life Vasya will get from eating this cake (1 \le F \le 30), and is the height of this cake in feet (1 \le H \le 25).
In the output file, print the minimum number of hours needed for Vasya to escape. If escape is impossible, print the maximum number of hours he can survive.
Example 1