CF865B Ordering Pizza

又到了 Start\[c\]up 总决赛的时候，这就意味着现场选手们需要订购比萨了。现在假设只有两种类型的比萨（当然实际不止两种，但为便于题目描述我们假定如此），且每个比萨恰好切成 $S$ 片。 已知第 $i$ 位选手会吃掉 $s_i$ 片比萨，每吃一片 1 号类型的比萨能获得 $a_i$ 点快乐值，每吃一片 2 号类型的比萨能获得 $b_i$ 点快乐值。我们可以订购任意数量的 1 号和 2 号比萨，但要求总订购的比萨数量最少，且每个选手都能吃到自己所需的片数。在这个前提下，可以获得的最大总快乐值是多少？

第一行包含整数 $N$ 和 $S$（$1 \leq N \leq 10^5, 1 \leq S \leq 10^5$），分别表示选手人数和每个比萨的分片数。 接下来的 $N$ 行，每行包含三个整数 $s_i$、$a_i$ 和 $b_i$（$1 \leq s_i \leq 10^5, 1 \leq a_i \leq 10^5, 1 \leq b_i \leq 10^5$），分别表示第 $i$ 位选手需要吃的比萨片数、每吃一片 1 号比萨获得的快乐值和每吃一片 2 号比萨获得的快乐值。

输出一个整数，表示在订购比萨数量最少的前提下所能获得的最大总快乐值。

在第一个样例中，只需要买一张比萨。如果买的是 1 号比萨，总快乐值为 $3\cdot 5 + 4\cdot 6 + 5\cdot 9 = 84$；如果买的是 2 号比萨，总快乐值为 $3\cdot 7 + 4\cdot 7 + 5\cdot 5 = 74$。 由 ChatGPT 5 翻译