[蓝桥杯 2024 省 A] 训练士兵

Luogu
IDLGP10387
Time1000ms
Memory512MB
DifficultyP2
贪心2024蓝桥杯省赛
在蓝桥王国中,有 $n$ 名士兵,这些士兵需要接受一系列特殊的训练,以提升他们的战斗技能。对于第 $i$ 名士兵来说,进行一次训练所需的成本为 $p_i$ 枚金币,而要想成为顶尖战士,他至少需要进行 $c_i$ 次训练。 为了确保训练的高效性,王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练,且总共只需支付 $S$ 枚金币(组团训练方案可以多次购买,即士兵可以进行多次组团训练)。 作为训练指挥官,请你计算出最少需要花费多少金币,才能使得所有的士兵都成为顶尖战士? ## Input 输入的第一行包含两个整数 $n$ 和 $S $,用一个空格分隔,表示士兵的数量和进行一次组团训练所需的金币数。 接下来的 $n$ 行,每行包含两个整数 $p_i$ 和 $c_i$,用一个空格分隔,表示第 $i$ 名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。 ## Output 输出一行包含一个整数,表示使所有士兵成为顶尖战士所需的最少金币数。 [samples] ## Note 花费金币最少的训练方式为:进行 $2$ 次组团训练,花费 $2 × 6 = 12$ 枚金币,此时士兵 $1, 3$ 已成为顶尖战士;再花费 $4$ 枚金币,让士兵 $2$ 进行两次训练,成为顶尖战士。总花费为 $12 + 4 = 16$。 对于 $40\%$ 的评测用例,$1 ≤ n ≤ 10^3,1 ≤ p_i , c_i ≤ 10^5,1 ≤ S ≤ 10^7$。 对于所有评测用例,$1 ≤ n ≤ 10^5,1 ≤ p_i , c_i ≤ 10^6,1 ≤ S ≤ 10^{10}$。
Samples
Input #1
3 6
5 2
2 4
3 2
Output #1
16
API Response (JSON)
{
  "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$ 枚金币(组团训练方案可以多次购买,即士兵可以进行多次组团训练)。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments