训练士兵

题号：NC309420
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

在蓝桥王国中，有 $n$ 名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第 $i$ 名士兵来说，进行一次训练所需的成本为 $p_i$ 枚金币，而要想成为顶尖战士，他至少需要进行 $c_i$ 次训练。

为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 $S$ 枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。

作为训练指挥官，请你计算出最少需要花费多少金币，才能使得所有的士兵成为顶尖战士？

输入描述:

输入的第一行包含两个整数  和 ，用一个空格分隔，表示士兵的数量和进行一次组团训练所需的金币数。

接下来  行，每行包含两个整数  和 ，用一个空格分隔，表示第  名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。

输出描述:

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

示例1

输入

复制

输出

复制

说明

花费金币最少的训练方式为：进行 2 次组团训练，花费  枚金币，此时士兵 1, 3 已成为顶尖战士；再花费 4 枚金币，让士兵 2 进行两次训练，成为顶尖战士。总花费为 。

备注:

- 对于 40% 的评测用例，。
- 对于所有评测用例，。