Fighting

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

怒海争锋是一个新游戏,类似于星际争霸。在这个游戏中,敌人建造防御塔,血量为L。玩家有一个军事工厂,可以生产N种战斗舰艇。第i个战舰的生产时间为ti,这战舰每秒钟可以让塔损失血量为li。如果塔的寿命低于或等于0,玩家获胜。注意,在每一秒内,军事工厂只能选择一种战斗船生产或什么也不做。选择后的战斗舰艇生产时不可以同时生产。生产完一个再生产下一个。
 
你的任务是找出玩家赢得比赛的最少时间。 

Input

有多组输入。  
每组的第一行包含两个整数N(1≤N≤30)和L (1≤L≤330),N是军事工厂中有N种战舰,L是防御塔的血量。然后以下N行,每一行包含两个整数ti(1≤ti≤20)第i个战舰的生产时间和li(1≤li≤330)第i个战斗舰艇对塔造成的伤害。

Output

为每个测试用例输出一行。一个整数表示玩家赢得比赛的最少时间。

Sample Input

1 1
1 1
3 100
1 10
3 20
10 100

Sample Output

2
5

Hint

 

Source

xfl