Description

You have given up programming and moved to the Sanjiang Plain to start farming. During your time working in the fields, you have adopted a regular daily schedule, and now you work $\textbf{exactly}$ $m$ units of time each day. It is now harvest season, and you need to harvest and process $n$ types of crops. For crop type $i$, processing it for one unit of time will yield a profit of $w_i$. To make your daily work less monotonous, for each crop type $i$, the time spent processing it each day can range between $[l_i, r_i]$ inclusive as an integer.

At some day, the weather forecast says that there will be a heavy rain tomorrow and you can't work, so you need to adjust your schedule to quickly gather your crops today. Specifically, you can choose at most one type of crop and remove its daily time range restriction, allowing the time spent processing this crop to be any integer in the range $[0, m]$. The time ranges for all other crops remain unchanged. You have to work $\textbf{exactly}$ $m$ units of time as well.

You want to determine the maximum profit you can earn today.

Input Format

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^{11}$), representing the number of crop types and the length of the workday in units of time, respectively.

The next $n$ lines each contain three integers $w_i$, $l_i$, and $r_i$ ($1 \le w_i \le 10^6$, $1 \le l_i \le r_i \le 10^6$), indicating the profits and time constraints of the crops.

It is guaranteed that $\sum_{i=1}^n l_i \le m \le \sum_{i=1}^n r_i$.

Output Format

Output a single integer representing the maximum profit you can earn today.

5 17
2 3 4
6 1 5
8 2 4
4 3 3
7 5 5

109