Guaranteed Worst-Case Profit

You have developed \(n\) types of experiments to obtain antimatter. In the \(i\)th experiment, the amount of antimatter produced is guaranteed to lie in the interval \([l_i, r_i]\), and the cost of the experiment is \(c_i\). You can perform each experiment an unlimited number of times.

All produced antimatter is stored in a container. After each experiment, you are informed of the total mass of antimatter in the container. However, the container can hold at most \(a\) grams of antimatter, and if the amount exceeds \(a\) the container will explode.

If in one experiment you obtain \(t_i\) units of antimatter, you can sell it to the military for a profit of \(10^9 \times t_i - c_i\) rubles. In the worst-case scenario, the amount obtained in each experiment is \(l_i\) (the lower bound of the interval).

Under the safety constraint (i.e. ensuring that the total worst-case antimatter never exceeds \(a\) grams), determine the maximum profit that you can guarantee in the worst-case.

inputFormat

The first line contains two integers \(n\) and \(a\) (\(1 \le n \le \text{?}\), \(1 \le a \le \text{?}\)) – the number of types of experiments and the container capacity in grams, respectively.

Each of the next \(n\) lines contains three integers \(l_i\), \(r_i\), and \(c_i\), where \(l_i\) and \(r_i\) denote the lower and upper bounds of the antimatter produced, and \(c_i\) is the cost of the experiment.

outputFormat

Output a single integer – the maximum guaranteed profit (in rubles) you can achieve under the worst-case scenario.

sample

2 10
1 3 5
2 4 8

9999999960