← 返回题目列表

Codeforces · 865/B

B. 订购披萨

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

这又是一场 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。