P5957 [POI 2017] Flappy Bird

`Flappy Bird` is a very popular casual game.

In the game, the bird starts at $(0,0)$. Its goal is to reach some point whose $x$-coordinate is $X$. Every second, you may choose to tap the screen. If you tap, the bird moves from $(x,y)$ to $(x+1,y+1)$. If you do not tap, the bird moves from $(x,y)$ to $(x+1,y-1)$. There are also $n$ obstacles in the game, each described by a triple $(x_i,a_i,b_i)$. This means that on the vertical line $x=x_i$, the parts with $y\le a_i$ or $y\ge b_i$ are obstacles. Touching an obstacle or even just grazing its boundary is considered a failure. Now, find the minimum number of taps needed for the bird to fly from $(0,0)$ to the destination.

The first line contains two integers $n, X$. The next $n$ lines each contain three integers $x_i, a_i, b_i$. The testdata guarantees that $x_i

If it is impossible to reach the destination no matter what you do, output `NIE`. Otherwise, output the minimum number of taps.

For $100\%$ of the testdata, $0\le n\le 500000$, $1\le X\le10^9$, $0