Flappy Bird: Minimum Clicks

In this problem, you are given a variant of the famous Flappy Bird game. The bird starts at position \((0,0)\) and its goal is to reach any position with horizontal coordinate \(X\). The bird moves as follows:

• If you click the screen at a second, the bird moves from \((x,y)\) to \((x+1,y+1)\).
• If you do not click, it moves from \((x,y)\) to \((x+1,y-1)\).

There are \(n\) obstacles in the game. Each obstacle is given by a triple \((x_i, a_i, b_i)\), meaning that at line \(x=x_i\) the parts of the vertical line with \(y\le a_i\) or \(y\ge b_i\) are obstacles. Note that touching the barrier (being exactly at \(y=a_i\) or \(y=b_i\)) is forbidden. In other words, when crossing the vertical line \(x=x_i\) the bird's \(y\)-coordinate must satisfy \[ a_i < y < b_i. \]

Your task is to determine the minimum number of clicks required so that the bird can fly from \((0,0)\) to some position with \(x=X\) without colliding with any obstacle.

Note that after \(X\) moves, if the bird was clicked exactly \(r\) times, its final position will be \((X, 2r-X)\). Use this fact along with the ability to control the order of clicks to find the answer.

inputFormat

The first line contains two integers \(X\) and \(n\) \( (1 \le X \le 10^9,\ 0 \le n \le 10^5)\), representing the target horizontal coordinate and the number of obstacles respectively.

Each of the next \(n\) lines contains three integers \(x_i, a_i, b_i\), describing an obstacle at \(x=x_i\) (\(0 < x_i < X\)) where the forbidden parts on the vertical line are \(y\le a_i\) or \(y\ge b_i\). It is guaranteed that for each obstacle, \(a_i < b_i\).

outputFormat

Output a single integer: the minimum number of clicks required to reach \(x=X\) safely. If it is impossible to avoid all obstacles, output -1.

sample

3 0

0