题目描述

墙有 $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

输入

1 10
8 1

输出

0

样例 2

输入

3 3
4 2
1 1
10 8

输出

3

解释
第一段放两名防御者，第三段放一名防御者。

数据范围与提示

对于所有数据：

• $1 \leqslant n \leqslant 10^5$
• $1 \leqslant s \leqslant 10^9$
• $1 \leqslant a_i \leqslant 10^9$
• $1 \leqslant k_i \leqslant 10^9$

子任务