题目描述
译自 ROI 2016 Day1 T1. Оборона крепости
墙有 $n$ 段，第 $i$ 段有 $a_i$ 人进攻，在第 $i$ 段上，一名防御者能击退 $k_i$ 名攻击者。若某段有 $x_i$ 人防守，进攻者不超过 $x_i\times k_i$ 人，则此段不会被攻破；若进攻者超过 $x_i\times k_i$ 人，则将有 $a_i-x_i\times k_i$ 人攻破该段。 请将 $s$ 名防御者分配到墙的各段上，使得攻破防守的攻击者尽可能少。
输入格式
第一行两个整数 $n,s$。
接下来 $n$ 行，每行两个整数，分别表示 $a_i, k_i$。
输出格式
输出一行一个整数，表示在最优方案下攻破防守的攻击者数量。
样例 1
input
1 10
8 1output
0
样例 2
input
3 3
4 2
1 1
10 8output
3
第一段放两名防御者，第二段放一名防御者。
数据范围与提示
对于所有数据，$1 ⩽ n ⩽ 10^5,$ $1 ⩽ s ⩽ 10^9,$ $1 ⩽ a_i ⩽ 10^9,$ $1 ⩽ k_i ⩽ 10^9.$
| 子任务 # | 分值 | $1 ⩽ n ⩽ $ | $1 ⩽ s ⩽ $ | $1 ⩽ a_i ⩽ $ | $k_i$ | 依赖子任务 |
|---|---|---|---|---|---|---|
| 1 | 17 | $100$ | $10000$ | $100$ | $k_i = 1$ | |
| 2 | 21 | $100$ | $10000$ | $100$ | $1 ⩽ k_i ⩽ 2$ | 1 |
| 3 | 23 | $100$ | $10000$ | $100$ | $1 ⩽ k_i ⩽ 100$ | 1, 2 |
| 4 | 39 | $10^5$ | $10^9$ | $10^9$ | $1 ⩽ k_i ⩽ 10^9$ | 1 – 3 |