这又是一场 Start[c]up 决赛,这意味着现场参赛者可以订购披萨。披萨只有两种类型(显然不是,但为了解决问题我们就假装一下),并且所有披萨都包含 S 片。
已知第i名参赛者将吃si片披萨,每吃一片1型披萨获得ai幸福感,每吃一片2型披萨获得bi幸福感。我们可以订购任意数量的 1 型和 2 型披萨,但我们希望购买尽可能少数量的披萨,以便所有参赛者都能吃到所需数量的披萨。考虑到这种限制,可以实现的最大可能的总幸福是多少?
输入
输入的第一行将包含整数 N 和 S (1 ≤ N ≤ 105, 1 ≤ S ≤ 105),分别是参赛者的数量和每个披萨的切片数。接下来是 N 行。
第 i 行包含整数 si、ai 和 bi (1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 105)、第 i 名参赛者将吃的切片数量、他们从每吃 1 类 1 片中获得的幸福感以及从每吃 2 类 2 类片中获得的幸福感。
输出
打印出可以实现的最大总幸福感。
示例
输入 #1
3 12 3 5 7 4 6 7 5 9 5
输出 #1
84
输入 #2
6 10 7 4 7 5 8 8 12 5 8 6 11 6 3 3 7 5 9 6
输出 #2
314
注意
在第一个示例中,您只需要购买一个披萨。如果您购买类型 1 披萨,总幸福感将为 3·5 + 4·6 + 5·9 = 84,如果您购买类型 2 披萨,总幸福感将为 3·7 + 4·7 + 5·5 = 74。