{"problem":{"name":"B. Ordering Pizza","description":{"content":"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)","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF866B"},"statements":[{"statement_type":"Markdown","content":"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.\n\nIt 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?\n\n## Input\n\nThe first line of input will contain integers _N_ and _S_ (1 ≤ _N_ ≤ 105, 1 ≤ _S_ ≤ 105), the number of contestants and the number of slices per pizza, respectively. _N_ lines follow.\n\nThe _i_\\-th such line contains integers _s__i_, _a__i_, and _b__i_ (1 ≤ _s__i_ ≤ 105, 1 ≤ _a__i_ ≤ 105, 1 ≤ _b__i_ ≤ 105), 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.\n\n## Output\n\nPrint the maximum total happiness that can be achieved.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"这是另一次 Start[c]up 决赛，意味着需要为现场参赛者订购披萨。只有两种类型的披萨（显然不是，但为了问题方便我们假设如此），且每份披萨恰好包含 #cf_span[S] 片。\n\n已知第 #cf_span[i] 位参赛者将食用 #cf_span[si] 片披萨，每吃一片第一类披萨获得 #cf_span[ai] 点幸福值，每吃一片第二类披萨获得 #cf_span[bi] 点幸福值。我们可以订购任意数量的第一类和第二类披萨，但要求购买的披萨总数尽可能少，以确保所有参赛者都能吃到他们所需的片数。在该限制下，能获得的最大总幸福值是多少？\n\n输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[S] #cf_span[(1 ≤ N ≤ 105, 1 ≤ S ≤ 105)]，分别表示参赛者人数和每份披萨的片数。接下来有 #cf_span[N] 行。\n\n第 #cf_span[i] 行包含三个整数 #cf_span[si], #cf_span[ai], 和 #cf_span[bi] #cf_span[(1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 105)]，分别表示第 #cf_span[i] 位参赛者将食用的片数、每片第一类披萨带来的幸福值、每片第二类披萨带来的幸福值。\n\n请输出能获得的最大总幸福值。\n\n在第一个例子中，你只需购买一份披萨。如果购买第一类披萨，总幸福值为 #cf_span[3·5 + 4·6 + 5·9 = 84]；如果购买第二类披萨，总幸福值为 #cf_span[3·7 + 4·7 + 5·5 = 74]。\n\n## Input\n\n输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[S] #cf_span[(1 ≤ N ≤ 105, 1 ≤ S ≤ 105)]，分别表示参赛者人数和每份披萨的片数。接下来有 #cf_span[N] 行。第 #cf_span[i] 行包含三个整数 #cf_span[si], #cf_span[ai], 和 #cf_span[bi] #cf_span[(1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 105)]，分别表示第 #cf_span[i] 位参赛者将食用的片数、每片第一类披萨带来的幸福值、每片第二类披萨带来的幸福值。\n\n## Output\n\n请输出能获得的最大总幸福值。\n\n[samples]\n\n## Note\n\n在第一个例子中，你只需购买一份披萨。如果购买第一类披萨，总幸福值为 #cf_span[3·5 + 4·6 + 5·9 = 84]；如果购买第二类披萨，总幸福值为 #cf_span[3·7 + 4·7 + 5·5 = 74]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, S \\in \\mathbb{Z}^+ $: number of contestants, slices per pizza.  \nFor each contestant $ i \\in \\{1, \\dots, N\\} $:  \n- $ s_i \\in \\mathbb{Z}^+ $: slices consumed,  \n- $ a_i \\in \\mathbb{Z}^+ $: happiness per slice of type 1 pizza,  \n- $ b_i \\in \\mathbb{Z}^+ $: happiness per slice of type 2 pizza.  \n\nLet $ x_i \\in [0, s_i] \\cap \\mathbb{Z} $: number of type 1 slices consumed by contestant $ i $,  \nthen $ s_i - x_i $: number of type 2 slices consumed by contestant $ i $.  \n\nLet $ T = \\sum_{i=1}^N s_i $: total slices required.  \nLet $ P = \\left\\lceil \\frac{T}{S} \\right\\rceil $: minimum number of pizzas needed.  \n\nLet $ p_1 \\in \\{0, 1, \\dots, P\\} $: number of type 1 pizzas ordered,  \nthen $ p_2 = P - p_1 $: number of type 2 pizzas ordered.  \n\nTotal type 1 slices available: $ p_1 \\cdot S $,  \ntotal type 2 slices available: $ p_2 \\cdot S $.  \n\n**Constraints**  \n1. $ \\sum_{i=1}^N x_i \\leq p_1 \\cdot S $  \n2. $ \\sum_{i=1}^N (s_i - x_i) \\leq p_2 \\cdot S $  \n3. $ p_1 + p_2 = P $  \n4. $ 0 \\leq x_i \\leq s_i $ for all $ i $  \n\n**Objective**  \nMaximize total happiness:  \n$$\n\\max_{\\substack{p_1 \\in \\{0,\\dots,P\\} \\\\ x_i \\in [0,s_i]}} \\sum_{i=1}^N \\left( x_i a_i + (s_i - x_i) b_i \\right)\n$$  \nsubject to the above constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF866B","tags":["greedy","implementation","sortings"],"sample_group":[["3 12\n3 5 7\n4 6 7\n5 9 5","84"],["6 10\n7 4 7\n5 8 8\n12 5 8\n6 11 6\n3 3 7\n5 9 6","314"]],"created_at":"2026-03-03 11:00:39"}}