P14205 [ROI 2016 Day1] 要塞防御

**译自 [ROI 2016](http://neerc.ifmo.ru/school/archive/2015-2016.html) Day1 T1.** ***[Оборона крепости](http://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-roi-2016-day1.pdf)***

被围困的要塞之墙由 $n$ 个防御段组成，这些防御段从 $1$ 到 $n$ 编号。侦察报告称，在下一次进攻中，敌人将派出 $a_i$ 名士兵进攻编号为 $i$ 的防御段。要塞共有 $s$ 名守卫，需要分配到这些防御段上。 不同的防御段加固程度不同，这导致了防守效率的差异。编号为 $i$ 的防御段上，每一名守卫都能抵御 $k_i$ 名进攻者。假设编号为 $i$ 的防御段上派遣了 $x_i$ 名守卫。那么，如果敌人的数量不超过 $x_i \cdot k_i$，则该段防线将完全守住，不会有敌人突破；否则，将有 $a_i - x_i \cdot k_i$ 名敌人突破防线，攻入要塞。 你的任务是编写一个程序，合理分配守卫人数，使得总人数恰好为 $s$，并使得突破要塞的敌人数最少。

输入的第一行包含两个整数 $n$ 和 $s$，分别表示防御段的数量和要塞的守卫总数（$1 \le n \le 100\,000$；$1 \le s \le 10^9$）。 接下来的 $n$ 行中，每行包含两个整数 $a_i, k_i$，分别表示进攻编号为 $i$ 的防御段的敌人总数，以及该段上每名守卫能够抵御的敌人数（$1 \le a_i, k_i \le 10^9$）。

输出一个整数——即最少能突破要塞的敌人数。

### 样例解释 在第一个测试中，如果将全部 $10$ 名守卫派往唯一的防御段，他们可以击退所有 $8$ 名敌人，因此不会有敌人突破防线。 在第二个测试中，一种可行的方案是将 $2$ 名守卫派往第一个防御段，将 $1$ 名守卫派往第三个防御段，这样可以使突破的敌人数量最小化。 ### 数据范围 | 子任务编号 | 分值 | $n$ | $s$ | $a$ | $k$ | 必须通过的子任务 | |:-----------:|:----:|:---:|:---:|:---:|:---:|:----------------:| | 1 | 17 | $1 \le n \le 100$ | $1 \le s \le 10\,000$ | $1 \le a_i \le 100$ | $k_i = 1$ | | | 2 | 21 | $1 \le n \le 100$ | $1 \le s \le 10\,000$ | $1 \le a_i \le 100$ | $k_i \le 2$ | 1 | | 3 | 23 | $1 \le n \le 100$ | $1 \le s \le 10\,000$ | $1 \le a_i \le 100$ | $1 \le k_i \le 100$ | 1, 2 | | 4 | 39 | $1 \le n \le 100\,000$ | $1 \le s \le 10^9$ | $1 \le a_i \le 10^9$ | $1 \le k_i \le 10^9$ | 1, 2, 3 | 翻译由 ChatGPT-5 完成