题目背景

译自 ROI 2016 Day1 T1. Оборона крепости

题目描述

被围困的要塞之墙由 $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$）。

输出格式

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

1 10
8 1

0

3 3
4 2
1 1
10 8

3

提示

样例解释

在第一个测试中，如果将全部 $10$ 名守卫派往唯一的防御段，他们可以击退所有 $8$ 名敌人，因此不会有敌人突破防线。

在第二个测试中，一种可行的方案是将 $2$ 名守卫派往第一个防御段，将 $1$ 名守卫派往第三个防御段，这样可以使突破的敌人数量最小化。

数据范围

翻译由 ChatGPT-5 完成