题目描述

$小屿$ 有 $n$ 张卡牌和 $m$ 枚硬币，每张卡牌有正反两面，初始时全部正面朝上。 翻牌操作描述如下： 对于第 $i ( 1 \leq i \leq n )$ 张卡牌，当其正面朝上时，可以花费 $a_i$ 枚硬币将其翻面；反面朝上时，可以花费 $b_i$ 枚硬币将其翻面。（硬币不够花费时无法操作）。 现在 小屿 希望知道最多可以翻多少次牌，请输出这个值。

输入格式

第一行两个整数 $n , m$ 表示有 $n$ 张牌和 $m$ 枚硬币

随后 $n$ 行，第 $i$ 行两个数表示 $a_i ，b_i$

输出格式

一行一个整数，表示最多能翻多少次牌。

输入输出样例

2 10
4 1
3 3

4

提示

翻 $4$ 次第一张牌，总花费为 $4 + 1 + 4 + 1 = 10$

数据规模

对于$40\%$的测试数据：

$1 \leq n \leq 10^5$

$1 \leq m \leq 10^5$

对于全部的测试数据：

$1 \leq n \leq 10^5$

$1 \leq m \leq 10^{18}$

$1 \leq a_i,b_i \leq 10^9$