{"problem":{"name":"[蓝桥杯 2024 省 A] 训练士兵","description":{"content":"在蓝桥王国中，有 $n$ 名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第 $i$ 名士兵来说，进行一次训练所需的成本为 $p_i$ 枚金币，而要想成为顶尖战士，他至少需要进行 $c_i$ 次训练。   为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 $S$ 枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10387"},"statements":[{"statement_type":"Markdown","content":"在蓝桥王国中，有 $n$ 名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第 $i$ 名士兵来说，进行一次训练所需的成本为 $p_i$ 枚金币，而要想成为顶尖战士，他至少需要进行 $c_i$ 次训练。  \n为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 $S$ 枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。  \n作为训练指挥官，请你计算出最少需要花费多少金币，才能使得所有的士兵都成为顶尖战士？\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $S $，用一个空格分隔，表示士兵的数量和进行一次组团训练所需的金币数。  \n接下来的 $n$ 行，每行包含两个整数 $p_i$ 和 $c_i$，用一个空格分隔，表示第 $i$ 名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。\n\n## Output\n\n输出一行包含一个整数，表示使所有士兵成为顶尖战士所需的最少金币数。\n\n[samples]\n\n## Note\n\n花费金币最少的训练方式为：进行 $2$ 次组团训练，花费 $2 × 6 = 12$ 枚金币，此时士兵 $1, 3$ 已成为顶尖战士；再花费 $4$ 枚金币，让士兵 $2$ 进行两次训练，成为顶尖战士。总花费为 $12 + 4 = 16$。\n\n对于 $40\\%$ 的评测用例，$1 ≤ n ≤ 10^3，1 ≤ p_i\n, c_i ≤ 10^5，1 ≤ S ≤ 10^7$。\n\n对于所有评测用例，$1 ≤ n ≤ 10^5，1 ≤ p_i\n, c_i ≤ 10^6，1 ≤ S ≤ 10^{10}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10387","tags":["贪心","2024","蓝桥杯省赛"],"sample_group":[["3 6\n5 2\n2 4\n3 2","16"]],"created_at":"2026-03-03 11:09:25"}}