{"problem":{"name":"[厦门小学生 C++ 2025] 矿石开采","description":{"content":"星际矿业公司在某星球发现了 $ n $ 座矿石矿脉，每座矿脉初始蕴含 $ a_i $ 单位的高纯度矿石量。每次对第 $ i $ 座矿脉开采时，可获得一定的收益，收益与当前矿脉的矿石量相同。开采后该矿脉的矿石量会减少 $ b_i $ 单位（当剩余量不足 $ b_i $ 时，减少至 $ 0 $，此后无法再开采矿石获得收益）。 由于星际开采能力有限，最多只能进行 $ k $ 次开采操作（每次操作可选择","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4473"},"statements":[{"statement_type":"Markdown","content":"星际矿业公司在某星球发现了 $ n $ 座矿石矿脉，每座矿脉初始蕴含 $ a_i $ 单位的高纯度矿石量。每次对第 $ i $ 座矿脉开采时，可获得一定的收益，收益与当前矿脉的矿石量相同。开采后该矿脉的矿石量会减少 $ b_i $ 单位（当剩余量不足 $ b_i $ 时，减少至 $ 0 $，此后无法再开采矿石获得收益）。\n\n由于星际开采能力有限，最多只能进行 $ k $ 次开采操作（每次操作可选择此星球中任意一座矿脉进行开采）。为了最大化收益，公司需要制定最优的开采策略，确保在不超过 $ k $ 次操作的前提下，获取的总收益尽可能多。\n\n已知共有 $ t $ 个星球的矿脉数据需要处理，每个星球的矿脉情况独立，请你计算在每个星球中采矿所能获取的最大收益。\n\n## Input\n\n第一行输入一个整数 $ t $（$ 1 \\leq t \\leq 1000 $），表示星球的数量。\n\n对于每个星球，输入格式如下：\n\n第一行输入两个整数 $ n $ 和 $ k $（$ 1 \\leq n \\leq 10^5 $，$ 1 \\leq k \\leq 10^9 $），分别表示矿脉数量和最大开采次数。\n\n第二行输入 $ n $ 个整数 $ a_1, a_2, \\ldots, a_n $（$ 1 \\leq a_i \\leq 10^9 $），表示每座矿脉的初始高纯度矿石量。\n\n第三行输入 $ n $ 个整数 $ b_1, b_2, \\ldots, b_n $（$ 1 \\leq b_i \\leq 10^9 $），表示每座矿脉每次开采后的减少量。\n\n保证每个星球中 $ n $ 的总和不超过 $ 2 \\times 10^5 $。\n\n## Output\n\n对于每个星球，输出一行整数，表示在每个星球中采矿所能获取的最大收益。\n\n[samples]\n\n## Note\n\n### 【样例解释】\n\n对于此样例中的 $5$ 个星球中的第一个星球，三个矿脉采集的次数可以为 $ (1, 1, 2) $ 或 $ (1, 2, 1) $ 或 $ (2, 1, 1) $，获得的最大收益为 $ 7 + 6 + 5 + 3 = 21 $。\n\n### 【数据范围】\n\n对于所有数据，满足 $ 1 \\leq t \\leq 1000 $，$ 1 \\leq n \\leq 10^5 $，$ 1 \\leq k \\leq 10^9 $，$ 1 \\leq a_i, b_i \\leq 10^9 $，且每个星球中 $ n $ 的总和不超过 $ 2 \\times 10^5 $。\n\n::cute-table{tuack}\n\n| 测试点 | $ t \\leq $ | $ n \\leq $ | $ k \\leq $ | $ a_i, b_i \\leq $ |\n|:-:|:-:|:-:|:-:|:-:|\n| $1\\sim 2$ | $ 10^2 $ | $ 10^3 $ | $ 10^2 $ | $ 10^3 $ |\n| $1\\sim 5$ | $ 200 $ | $ 10^4 $ | $ 50000 $ | $ 10^6 $ |\n| $1\\sim 10$ | $ 10^3 $ | $ 10^5 $ | $ 10^9 $ | $ 10^9 $ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4473","tags":["数学","二分","2025","小学活动"],"sample_group":[["5\n3 4\n5 6 7\n2 3 4\n5 9\n32 52 68 64 14\n18 14 53 24 8\n5 1000\n1 2 3 4 5\n5 4 3 2 1\n1 1000000\n1000000\n1\n10 6\n3 3 5 10 6 8 6 8 7 7\n6 1 7 4 1 1 8 9 3 1","21\n349\n27\n500000500000\n47"]],"created_at":"2026-03-03 11:09:25"}}