Problem Description

You have developed $n$ experiments to obtain antimatter. You cannot control the quantity generated, but you can ensure that the antimatter produced by the $i$-th experiment falls within the interval $[l_i, r_i]$, with a cost of $c_i$. Each experiment can be used multiple times.

The generated antimatter is stored in a container. After each experiment, you can determine the mass of antimatter in the container. The container cannot hold more than $a$ grams of antimatter (exceeding this limit will cause an explosion).

If the $i$-th experiment yields $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 the experiment.

Under the premise of safety, you want to know the minimum profit you can guarantee in the worst-case scenario.

Input Format

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

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

Output Format

Output a single integer, representing the maximum profit you can guarantee.

Sample Input and Output

Sample Input #1

1 17
4 6 10

Sample Output #1

11999999970

Sample Input #2

2 11
2 2 100
3 5 5

Sample Output #2

9999999890

Notes/Hints

Sample Explanation

For Sample #1:

We can only use Experiment 1. If we conduct it once, the resulting antimatter is within $[4, 6]$; if we conduct it twice, the range is $[8, 12]$. If we obtain 12 units at this point, we cannot continue the experiment because if we get 6 units next time, the container will explode; otherwise, we can proceed with a third experiment, with a possible range of $[12, 17]$.

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

Data Range

This problem only provides partial data. For complete data evaluation, please visit LOJ P2772.

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

Note: The original problem had 15 subtasks. For convenience, several subtasks with the same constraints except for the data range of $a$ have been merged into one subtask.

见题面 Input 部分

见题面 Output 部分