B. Colored Ring
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There's a colored ring on the table. The ring has $$$k$$$ sectors, and $$$i$$$-th sector has color $$$i$$$ (all $$$k$$$ colors are pairwise distinct). Sectors are numbered consecutively in clockwise direction. Kanga allowed Baby Roo to write $$$n$$$ different integers from $$$1$$$ to $$$n$$$ on the ring. Number $$$i$$$ should be written either on sector with color $$$x_i$$$, said Kanga, or on any other that is at most $$$a_i$$$ sectors counterclockwise far from $$$x_i$$$ or at most $$$b_i$$$ sectors clockwise far.

Kanga said that the numbers are written correctly if the above restrictions are met, each sector has at most one number written on it and the numbers $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n$$$ are ordered in clockwise direction: if we start from the sector where $$$1$$$ is written and then go clockwise, the all other numbers are met in order $$$2$$$, $$$3$$$, $$$\ldots$$$, $$$n$$$ and then $$$1$$$ again.

After all numbers are written correctly, all sectors with a number will be spoiled. Now Baby Roo wants to know how many different ways are there to spoil the colored ring. Please note that it doesn't matter what number you write on the sector to get it spoiled.

Input

First line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 15$$$, $$$1 \leq k \leq 60$$$, $$$n \leq k$$$). Each of the next $$$n$$$ lines contains three integers $$$x_i$$$, $$$a_i$$$, $$$b_i$$$ ($$$1 \leq x_i \leq k$$$; $$$0 \leq a_i, b_i$$$; $$$a_i + b_i \lt k$$$). The numbers $$$x_i$$$ are sorted in strictly increasing order.

Output

Output the number of different ways to spoil the ring.

Examples
Input
1 5
1 2 1
Output
4
Input
3 8
4 0 3
5 0 3
6 0 0
Output
3
Input
3 7
2 2 4
4 1 3
6 1 5
Output
35