Ordering Pizza

题意翻译

CF865B Ordering Pizza 题意: 这儿有两种披萨,每份披萨分为了S块.第i个人将会吃掉Si块披萨,并且获得一些幸运值,若吃第一种披萨,每吃一块将会获得ai点幸运值,若吃第二种披萨,每吃一块将会获得bi点幸运值.我们可以任意点餐,但是最好的结果是,购买最少份数的披萨使得所有人吃上他们想要的份数.根据这个要求,能获得的最大的幸运值是多少? 输入: 第一行两个整数N,S(1<=N,S<=10^5),分别表示人数和每份披萨分成的块数. 接下来N行,每行三个整数s,a,b(1<=s,a,b<=10^5),分别表示第i个人想吃的块数,以及两种幸运值. 输出: 能获得的最大的幸运值. 翻译贡献者UID：36080

题目描述

It's another Start\[c\]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem), and all pizzas contain exactly $ S $ slices. It is known that the $ i $ -th contestant will eat $ s_{i} $ slices of pizza, and gain $ a_{i} $ happiness for each slice of type 1 pizza they eat, and $ b_{i} $ happiness for each slice of type 2 pizza they eat. We can order any number of type 1 and type 2 pizzas, but we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices. Given that restriction, what is the maximum possible total happiness that can be achieved?

输入输出格式

输入格式

The first line of input will contain integers $ N $ and $ S $ $ (1<=N<=10^{5},1<=S<=10^{5}) $ , the number of contestants and the number of slices per pizza, respectively. $ N $ lines follow. The $ i $ -th such line contains integers $ s_{i} $ , $ a_{i} $ , and $ b_{i} $ $ (1<=s_{i}<=10^{5},1<=a_{i}<=10^{5},1<=b_{i}<=10^{5}) $ , the number of slices the $ i $ -th contestant will eat, the happiness they will gain from each type 1 slice they eat, and the happiness they will gain from each type 2 slice they eat, respectively.

输出格式

Print the maximum total happiness that can be achieved.

输入输出样例

输入样例 #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

说明

In the first example, you only need to buy one pizza. If you buy a type 1 pizza, the total happiness will be $ 3·5+4·6+5·9=84 $ , and if you buy a type 2 pizza, the total happiness will be $ 3·7+4·7+5·5=74 $ .