← 返回题目列表

Codeforces · 1211/C

C. 冰淇淋

中文机器翻译题面 查看原题

Berland的夏天持续$$$n$$$天,第$$$i$$$天一份冰淇淋的价格是$$$c_i$$$。整个夏天,Tanya 只想吃 $$$k$$$ 份的冰淇淋。同时,在第 $$$i$$$ 天,她决定至少吃 $$$a_i$$$ 份,但不超过 $$$b_i$$$ ($$$a_i \le b_i$$$) 份。换句话说,令 $$$d_i$$$ 等于她在第 $$$i$$$ 日吃的份数。然后 $$$d_1+d_2+\dots+d_n=k$$$ 和 $$$a_i \le d_i \le b_i$$$ 对于每个 $$$i$$$。

鉴于部分冰淇淋只能在购买当天食用,请找出 Tanya 在夏天可以花在冰淇淋上的最低金额。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$0 \le k \le 10^9$$$) — Tanya 在夏天吃冰淇淋的天数和总份数。

以下 $$$n$$$ 行包含对日期的描述,每行一个描述。每个描述由三个整数 $$$a_i, b_i, c_i$$$ ($$$0 \le a_i \le b_i \le 10^9$$$, $$$1 \le c_i \le 10^6$$$) 组成。

输出

打印出 Tanya 在夏天可以花在冰淇淋上的最低金额。如果Tanya无法购买并满足所有要求,则打印-1。

示例

输入 #1

3 7
3 5 6
0 3 4
3 3 3

输出 #1

31

输入 #2

1 45000
40000 50000 100000

输出 #2

4500000000

输入 #3

3 100
2 10 50
50 60 16
20 21 25

输出 #3

-1

输入#4

4 12
2 5 1
1 2 2
2 3 7
3 10 4

输出#4

35

注意

在第一个示例中,Tanya 第一天需要吃 $$$3$$$ 份冰淇淋,第二天需要吃 $$$1$$$ 份冰淇淋,第三天需要吃 $$$3$$$ 份冰淇淋。在这种情况下,花费的金额为$$$3\cdot6+1\cdot4+3\cdot3=31$$$。可以证明,任何其他有效的方式吃掉 $$$7$$$ 份的冰淇淋都会花费更多。