A company is testing a technology for producing antimatter, which is used as fuel in an interplanetary starship. Antimatter is produced as a result of special experiments in a reactor.

There are $n$ known types of experiments that result in the production of antimatter. As a result of performing an experiment of type $i$, between $l_i$ and $r_i$ grams of antimatter are added to the reactor's output container. For safety reasons, it is forbidden to accumulate more than $a$ grams of antimatter in the container.

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

If, after performing experiments, $t$ grams of antimatter have accumulated in the container, and the total cost of performing the experiments in the reactor is $s$, then the profit is determined by the formula $(t \cdot 10^9 - s)$. The company needs to develop a strategy for conducting experiments that allows for maximizing the profit that can be guaranteed.

Depending on the results of previous experiments, the strategy determines which type of experiment to perform, or decides to stop further experiments. A strategy allows for a guaranteed profit of $x$ if, for any results of the experiments: first, there is no more than $a$ grams of antimatter in the reactor container, and second, the profit is at least $x$.

For example, suppose only one type of experiment is possible, producing from 4 to 6 grams of antimatter, the cost of performing it is 10, and the container capacity is 17 grams. Then, after performing the experiment twice, there may be from 8 to 12 grams of antimatter in the container. If 12 grams were obtained, the experiment cannot be performed again, because in the case of obtaining 6 grams of antimatter, the container might overflow. In other cases, one can perform the experiment a third time and obtain from 12 to 17 grams of antimatter. In the worst case, one would have to perform the experiment three times, spending a total of 30, and the profit would be $(12 \cdot 10^9 - 30) = 11\,999\,999\,970$.

You are required to 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 allowable amount of antimatter in the container ($1 \le n \le 100$, $1 \le a \le 2\,000\,000$).

The following $n$ lines contain three integers each: $l_i$, $r_i$, and $c_i$ — the minimum and maximum amount of antimatter obtained as a result of an experiment of type $i$, and the cost of an experiment of this type, respectively ($1 \le l_i \le r_i \le a$, $1 \le c_i \le 100$).

Output

The output must contain a single 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