T563204 「2025 YAC Round 2」训练无垢者

「2025 YAC Round 2」B 题

在阿斯塔波的善主领导下，无垢者正在进行严格的训练，以成为顶尖的战士。为了提升他们的战斗技能，善主安排了不同的训练计划，并且每名无垢者的训练成本和所需次数各不相同。 设定如下： 有 $n$ 名无垢者，每个无垢者的训练费用各不相同。 对于第 $i$ 名无垢者来说，每次训练的费用为 $p_i$ 枚金币，而他至少需要进行 $c_i$ 次训练才能成为顶尖战士。 善主推出了一种组团训练的方案，这种方案每次购买能够同时训练所有无垢者一次，总共花费 $S$ 枚金币（该方案可以多次购买，每名无垢者可以多次参加组团训练）。 请计算最少需要花费多少金币，才能确保所有无垢者都完成所需的训练次数，成为顶尖战士。

输入的第一行包含两个整数 $n$ 和 $S$，用一个空格分隔，表示无垢者的数量和进行一次组团训练所需的金币数。 接下来的 $n$ 行，每行包含两个整数 $p_i$ 和 $c_i$，用一个空格分隔，表示第 $i$ 名无垢者进行一次训练的金币成本和要成为顶尖战士所需的训练次数。

输出一行包含一个整数，表示使所有无垢者成为顶尖战士所需的最少金币数。

花费金币最少的训练方式为：进行 $2$ 次组团训练，花费 $2 × 6 = 12$ 枚金币，此时无垢者 $1, 3$ 已成为顶尖战士；再花费 $4$ 枚金币，让无垢者 $2$ 进行两次训练，成为顶尖战士。总花费为 $12 + 4 = 16$。 对于所有评测用例，$1 ≤ n ≤ 10^5，1 ≤ p_i , c_i ≤ 10^6，1 ≤ S ≤ 10^{10}$。