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$$$ 份的冰淇淋都会花费更多。