{"problem":{"name":"J. Jenny and the Batteries","description":{"content":"Jenny works at BBB (Battery Bank of Brazil). She's in charge of optimizing the batteries' displacements, but can't solve the problem. Knowing you are a programmer, she asked for your help. At BBB, th","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10162J"},"statements":[{"statement_type":"Markdown","content":"Jenny works at BBB (Battery Bank of Brazil). She's in charge of optimizing the batteries' displacements, but can't solve the problem. Knowing you are a programmer, she asked for your help.\n\nAt BBB, the batteries are arranged in piles. In a bank, the batteries can't be discharged. So, when recharging then, the bank spends M energy units, where M is the size of the greatest pile. Each pile initially has ai batteries.\n\nThere is a machine the can move a battery from pile i to pile j with cost bi + cj. Jenny has a limited budget of K for moving the batteries and the bank wants the minimum M possible at the end.\n\nThe first line of input consists of the integers N and K (1 ≤ N ≤ 105, 1 ≤ K ≤ 1018). The following N lines contain ai, bi and ci (0 ≤ ai, bi, ci ≤ 106).\n\nPrint the minumum M possible.\n\n## Input\n\nThe first line of input consists of the integers N and K (1 ≤ N ≤ 105, 1 ≤ K ≤ 1018). The following N lines contain ai, bi and ci (0 ≤ ai, bi, ci ≤ 106).\n\n## Output\n\nPrint the minumum M possible.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of piles.  \nLet $ K \\in \\mathbb{Z}^+ $ be the budget for battery movements.  \nFor each pile $ i \\in \\{1, \\dots, N\\} $:  \n- $ a_i \\in \\mathbb{Z}_{\\geq 0} $: initial number of batteries.  \n- $ b_i \\in \\mathbb{Z}_{\\geq 0} $: cost to remove one battery from pile $ i $.  \n- $ c_i \\in \\mathbb{Z}_{\\geq 0} $: cost to add one battery to pile $ i $.  \n\nLet $ x_i \\in \\mathbb{Z}_{\\geq 0} $ be the final number of batteries in pile $ i $.  \nLet $ M = \\max_{i} x_i $ be the maximum pile size after movements.\n\n**Constraints**  \n1. $ \\sum_{i=1}^N x_i = \\sum_{i=1}^N a_i $ (total batteries conserved).  \n2. The total movement cost satisfies:  \n$$\n\\sum_{i=1}^N b_i (a_i - x_i)^+ + \\sum_{i=1}^N c_i (x_i - a_i)^+ \\leq K\n$$  \nwhere $ (z)^+ = \\max(0, z) $.  \n3. $ x_i \\geq 0 $ for all $ i $.\n\n**Objective**  \nMinimize $ M = \\max_{i} x_i $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10162J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}