Background

Special for beginners, ^_^

Description

小R又要打怪兽了。怪兽刚开始有h点生命值，小R有n个魔法可以用来打怪兽。第i个魔法可以对怪兽造成d_i伤害，如果怪兽的生命值≤d_i，那么它会死亡。否则它的生命值会减少d_i，但是第i个魔法还有一个副作用，就是如果它不能杀死怪兽的话，那么怪兽再受到d_i伤害后，生命值又会增加r_i（即生命值变成x-d_i+r_i，其中x是使用魔法前怪兽的生命值）。
例如怪兽原来的生命值是9，一个魔法d=5,r=1，使用一次魔法后，怪兽剩5点生命值，使用第二次时因为d_i刚好位5，所以怪兽直接死亡。
现在小R可以使用任意种类的魔法任意多次，问小R至少要使用多少次魔法杀死这只怪兽。如果永远无法杀死怪兽，输出-1。

Format

Input

第一行两个正整数n,h(n≤100,h≤10^18)
接下来每行两个正整数d_i,r_i (d_i,r_i≤10^9)描述第i种魔法。

Output

输出一行答案，如果无法杀死怪兽，输出-1。

Sample 1

Input

29
51
42

Output

2

Limitation

1s, 512MB for each test case.

Hint

对于30%的数据，n≤5,h≤10,d_i,r_i≤10
对于70%的数据，0≤A_i≤1,0≤X≤1
对于100%的数据，T≤30,n≤10000,0≤a_i,X≤10^9,K≤n

C++ Code

#include<bits/stdc++.h>
using namespace std;

int k=0,q=0;

int main() {
    freopen("monster.in","r",stdin);
    freopen("monster.out","w",stdout);
    int n;
    cin>>n;
    int m,x;
    int a,b;
    while(n--) {
        cin>>m>>x;
        k=0;
        q=0;
        while(m--) {
            cin>>a>>b;
            q=max(q,a);
            k=max(k,a-b);
        }
        if(q>=x)cout<<1<<'\n';
        else if(k==0)cout<<-1<<'\n';
        else cout<<(x-q+k-1)/k+1<<'\n';
    }
}

Source

CXJY 1001