Problem Description

You have developed $n$ types of experiments to obtain antimatter. You cannot control the amount produced, but you can guarantee that the amount of antimatter obtained by the $i$-th type lies within the interval $[l_i,r_i]$, and the cost is $c_i$. Each experiment type can be used multiple times.

All produced antimatter is stored in a container. After each experiment, you can learn the mass of antimatter in the container. The antimatter in the container must not exceed $a$ grams (otherwise it will explode).

If in the $i$-th run of an experiment you obtain a total of $t_i$ units of antimatter, you can sell it to the military for a profit of $(10^9t_i-c)$ rubles, where $c$ is the cost of that experiment.

Under the condition of ensuring safety, you want to know, in the worst case, what is the minimum profit you can guarantee.

Input Format

The first line contains two integers $n,a$.

The next $n$ lines each contain three integers $l_i,r_i,c_i$.

Output Format

Output one line with one integer, indicating the maximum profit you can guarantee.

1 17
4 6 10

11999999970

2 11
2 2 100
3 5 5

9999999890

Hint

Sample Explanation

For sample set #1:

We can only use experiment $1$. If we run it once, the antimatter obtained lies in $[4,6]$; if we run it twice, it lies in $[8,12]$. If we have obtained $12$ units of antimatter at this time, we cannot continue, because if the next run yields $6$ units, the container will explode. In other cases, we can continue with a third run, and the possible interval becomes $[12,17]$.

At this point, no matter what, we cannot continue, for the same reason as above. So in the worst case we can only obtain $12$ units of antimatter and need to run the experiment three times. The profit is $3 \times (10^9 \times 4-10)=11999999970$.

Constraints

Only part of the testdata is provided for this problem. If you need to judge against the full testdata, please go to LOJ P2772.

For all testdata, $1 \le c_i \le 100$, $1 \le l_i \le r_i \le a$.

Note: The original problem has $15$ subtasks. For convenience, the last several subtasks that are identical except for the constraint on $a$ are merged into one subtask here.

Translated by ChatGPT 5