Background

你正在玩一款小游戏。

你一共有n个技能，每个技能可以释放多次，第i个技能在释放后会让怪物持续掉血$ti$秒，每秒掉血量$di$。比如在第$j$秒释放这个技能，那么怪物会在第$j$秒到第$j+ti-1$秒掉血。

怪物一共有h点血量，血量在某个回合降到0或以下就算死亡，请求出怪物最早死亡的时间。

Format

Input

第一行两个整数n,h

接下来n行每行两个整数ti,di

Output

输出答案，保证怪物会死亡。

Samples

2 20
2 2
5 1

6

10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4

9

Limitation

对于10%的数据，保证$ti = 1$

对于另外10%的数据，保证$1 \leq ti \leq 2$

对于另外20%的数据，保证$1 \leq ti \leq 10$

对于另外20%的数据，保证所有的$di$相同

对于100%的数据，保证$1 \leq n \leq 3 \times 10^5$，$1 \leq h \leq 10^{18}$，$1 \leq ti,di \leq 10^9$