题目背景

基础算法思维赛的 $D$ 题。

题目描述

现有 $n$ 个商人打算在小 C 的集市出售商品，第 $i$ 位商人的商品单价为 $a_i$，并拥有 $b_i$ 件商品。 为了保证公平竞争，小 C 决定限制每位商人可以出售的商品数量上限 $k$。对于第 $i$ 位商人，如果 $b_i \leq k$，则他可以出售 $b_i$ 件商品，否则他只能出售 $k$ 件商品。

小 C 同时希望保证交易总额大于等于 $m$。他想知道在保证交易总额大于等于 $m$ 的前提下可以设置的最小的 $k$。

输入格式

输入多行。

第一行两个数 $n,m$，表示商人数量和交易总额限制；

接下来 $n$ 行，每行两个数字$a_i,b_i$表示商品单价和商品数量。

输出格式

输出一行。

一个数表示答案。

样例 #1

样例输入 #1

3 142
5 6
18 6
14 2

样例输出 #1

5

提示

数据范围】：

对于 $60 \%$ 的数据，$n, b_i \leq 1000$；

对于 $100 \%$ 的数据，$n \leq 10^5$，$a_i \leq 10^6$，$b_i \leq 10^7$，保证数据有解。