Pengu's Journey to Squeaky

Pengu wants to visit his friend Squeaky, who lives D kilometers away. His vehicle starts with F liters of fuel and consumes 1 liter per kilometer. The vehicle can hold an unlimited amount of fuel. There are N gas stations between his home and the destination. The i-th gas station is located at X_i kilometers from his home. At the i-th station, Pengu is allowed to refuel at most A_i liters, but only if his initial fuel F satisfies \[ F \le B_i \] (the station only serves vehicles with low enough initial fuel as an anti-hoarding mechanism).

Pengu can refuel at any station that meets the condition. When reaching a station, he first consumes fuel for the travel from his last position, and if the station's condition holds then he immediately refuels by adding up to A_i liters.

The problem is to determine the minimum initial fuel F such that Pengu can travel from his home (position 0) to Squeaky's house (position D) by possibly refueling at the stations along the way.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input begins with two integers D and N separated by a space, where D is the total distance and N is the number of gas stations. Following this, there are N lines. The i-th line contains three integers: X_i, A_i, and B_i, representing the location of the station, the maximum fuel amount that can be added at that station, and the threshold for the initial fuel under which refueling is allowed, respectively.

Format:
D N
X₁ A₁ B₁
X₂ A₂ B₂
...
Xₙ Aₙ Bₙ

outputFormat

Output a single integer representing the minimum initial fuel F that allows Pengu to complete the journey.

sample

10 2
3 4 5
6 2 10

4