A company is testing a technology for producing antimatter to be used as fuel in an interplanetary starship. Antimatter is produced by special experiments in a reactor.

There are $n$ known types of experiments that produce antimatter. An experiment of type $i$ adds between $l_i$ and $r_i$ grams of antimatter to the reactor's output container. For safety reasons, accumulating more than $a$ grams of antimatter in the container is forbidden.

The cost of an experiment of type $i$ is $c_i$, and the value of one gram of the antimatter produced is $10^9$.

If the experiments produce $t$ grams of antimatter in the container and the total cost of the experiments in the reactor is $s$, the profit is given by the formula $(t\cdot10^9-s)$. The company needs to develop a strategy for conducting experiments that maximizes the profit that can be guaranteed.

Depending on the results of previous experiments, the strategy determines which type of experiment to conduct or decides to stop conducting experiments. A strategy guarantees a profit of $x$ if, for every possible outcome of the experiments, first, the reactor's container holds no more than $a$ grams of antimatter, and second, the profit is at least $x$.

For example, suppose there is only one type of experiment, producing between $4$ and $6$ grams of antimatter, with a cost of $10$, and the container's capacity is $17$ grams. After conducting the experiment twice, the container may hold between $8$ and $12$ grams of antimatter. If $12$ grams have been produced, no further experiment can be conducted, because producing another $6$ grams could overflow the container. In all other cases, the experiment can be conducted a third time, resulting in between $12$ and $17$ grams of antimatter. In the worst case, the experiment must be conducted three times, with a total cost of $30$, and the profit is $(12\cdot10^9-30)=11\,999\,999\,970$.

Write a program that determines the maximum profit $x$ that can be guaranteed.

Input

The first line of the input contains two integers: $n$, the number of experiment types, and $a$, the maximum allowed amount of antimatter in the container ($1\le n\le100$, $1\le a\le2\,000\,000$).

Each of the next $n$ lines contains three integers $l_i$, $r_i$, and $c_i$: respectively, the minimum and maximum amounts of antimatter produced by an experiment of type $i$, and the cost of an experiment of that type ($1\le l_i\le r_i\le a$, $1\le c_i\le100$).

Output

The output must contain one integer: the maximum profit $x$ that can be guaranteed.

Examples

Input 1

1 17
4 6 10

Output 1

11999999970

Input 2

2 11
2 2 100
3 5 5

Output 2

9999999890

Subtasks