A12783 | Ice Cream

Summer in Berland lasts $n$ days, the price of one portion of ice cream on the $i$ -th day is $c_i$ . Over the summer, Tanya wants to eat exactly $k$ portions of ice cream. At the same time, on the $i$ -th day, she decided that she would eat at least $a_i$ portions, but not more than $b_i$ ( $a_i \le b_i$ ) portions. In other words, let $d_i$ be equal to the number of portions that she eats on the $i$ -th day. Then $d_1+d_2+\dots+d_n=k$ and $a_i \le d_i \le b_i$ for each $i$ .

Given that portions of ice cream can only be eaten on the day of purchase, find the minimum amount of money that Tanya can spend on ice cream in the summer.

The first line contains two integers $n$ and $k$ ( $1 \le n \le 2\cdot10^5$ , $0 \le k \le 10^9$ ) — the number of days and the total number of servings of ice cream that Tanya will eat in the summer.

The following $n$ lines contain descriptions of the days, one description per line. Each description consists of three integers $a_i, b_i, c_i$ ( $0 \le a_i \le b_i \le 10^9$ , $1 \le c_i \le 10^6$ ).

Print the minimum amount of money that Tanya can spend on ice cream in the summer. If there is no way for Tanya to buy and satisfy all the requirements, then print -1.