You are fighting with Zmei Gorynich — a ferocious monster from Slavic myths, a huge dragon-like reptile with multiple heads! 

 $m$ 

Initially Zmei Gorynich has $x$ heads. You can deal $n$ types of blows. If you deal a blow of the $i$-th type, you decrease the number of Gorynich's heads by $min(d_i, curX)$, there $curX$ is the current number of heads. But if after this blow Zmei Gorynich has at least one head, he grows $h_i$ new heads. If $curX = 0$ then Gorynich is defeated. 

You can deal each blow any number of times, in any order.

For example, if $curX = 10$, $d = 7$, $h = 10$ then the number of heads changes to $13$ (you cut $7$ heads off, but then Zmei grows $10$ new ones), but if $curX = 10$, $d = 11$, $h = 100$ then number of heads changes to $0$ and Zmei Gorynich is considered defeated.

Calculate the minimum number of blows to defeat Zmei Gorynich!

You have to answer $t$ independent queries.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) – the number of queries.

The first line of each query contains two integers $n$ and $x$ ($1 \le n \le 100$, $1 \le x \le 10^9$) — the number of possible types of blows and the number of heads Zmei initially has, respectively.

The following $n$ lines of each query contain the descriptions of types of blows you can deal. The $i$-th line contains two integers $d_i$ and $h_i$ ($1 \le d_i, h_i \le 10^9$) — the description of the $i$-th blow.


-----Output-----

For each query print the minimum number of blows you have to deal to defeat Zmei Gorynich. 

If Zmei Gorynuch cannot be defeated print $-1$.


-----Example-----
Input
3
3 10
6 3
8 2
1 4
4 10
4 1
3 2
2 6
1 100
2 15
10 11
14 100

Output
2
3
-1



-----Note-----

In the first query you can deal the first blow (after that the number of heads changes to $10 - 6 + 3 = 7$), and then deal the second blow.

In the second query you just deal the first blow three times, and Zmei is defeated. 

In third query you can not defeat Zmei Gorynich. Maybe it's better to convince it to stop fighting?

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n, x = list(map(int, input().split()))
    A = []
    for _1 in range(n):
       d, h = list(map(int, input().split()))
       A.append([d, h])
    A.sort(reverse=True)
    if A[0][0] >= x:
        print(1)
    else:
        x -= A[0][0]
        mz = 0
        for d, h in A:
            mz = max(mz, d - h)
        if mz:
            print((x + mz - 1) // mz + 1)
        else:
            print(-1)


T = int(input())
for _ in range(T):
    n, x = list(map(int, input().split()))
    damage = []
    maxi = []
    for i in range(n):
        d, h = list(map(int, input().split()))
        maxi.append(d)
        damage.append(d-h)
    damage.sort(reverse=True)
    maxi.sort(reverse=True)

    if damage[0] <= 0 and maxi[0] < x:
        print(-1)
    else:
        if maxi[0] >= x:
            print(1)
        else:
            print((x-maxi[0]-1)//damage[0]+2)


for _ in range(int(input())):
    n, x = list(map(int, input().split()))
    md = me = 0
    for _ in range(n):
        d, h = list(map(int, input().split()))
        md = max(md, d)
        me = max(me, d - h)
    if md >= x:
        print(1)
    elif me:
        print((x - md - 1) // me + 2)
    else:
        print('-1')


import math

T = int(input())
for t in range(T):
    n, x = map(int, input().split())
    gs = [tuple(map(int, input().split())) for _ in range(n)]
    max_d = max(g[0] for g in gs)
    max_delta = max(g[0] - g[1] for g in gs)
    if x <= max_d:
        c = 1
    elif max_delta <= 0:
        c = -1
    else:
        c = math.ceil((x - max_d)/max_delta) + 1
    print(c)

from math import ceil
t = int(input())
ans = []
for _ in range(t):
    n, x = map(int, input().split())

    a = -1
    b = 0

    for i in range(n):
        d, h = map(int, input().split())
        a = max(a, d-h)
        b = max(b, d)
    if (x<=b):
        ans.append(1)
        continue
    elif (a<=0):
        ans.append(-1)
    else:
        x = x-b
        ans.append(ceil(x/a)+1)
for el in ans:
    print(el)

for _ in range(int(input())):
    n, x = list(map(int, input().split()))
    a = [list(map(int, input().split())) for _ in range(n)]
    max1, max2 = -float('inf'), -float('inf')
    for q in a:
        max1 = max(q[0], max1)
        max2 = max(max2, q[0]-q[1])
    if max1 >= x:
        print(1)
    elif max2 <= 0:
        print(-1)
    else:
        print((x-max1+max2-1)//max2+1)


t = int(input())
for i in range(t):
    n, x = (int(i) for i in input().split())
    mr = 0
    md = 0
    for j in range(n):
        d, h = (int(i) for i in input().split())
        md = max(d, md)
        mr = max(d - h, mr)
    x -= md
    if not mr and x > 0:
        print(-1)
    elif x <= 0:
        print(1)
    else:
        f = x // mr + 1
        if x % mr:
            f += 1
        print(f)


t = int(input())

for _ in range(t):
    n, x = list(map(int, input().split()))

    a = b = -1100100100100
    for i in range(n):
        d, h = list(map(int, input().split()))

        a = max(a, d - h)
        b = max(b, d)

    if x <= b:
        print(1)
    elif a <= 0:
        print(-1)
    else:
        x -= b
        print((x + a - 1) // a + 1)


T = int(input())
for i in range(0, T):
    k, x = (int(i) for i in input().split())
    best_diff = None
    max_strike = None
    for j in range(k):
        strike, heads = (int(i) for i in input().split())
        if max_strike is None or strike > max_strike:
            max_strike = strike
        if strike > heads and (best_diff is None or best_diff < strike - heads):
            best_diff = strike - heads
    x -= max_strike
    if x <= 0:
        print(1)
    elif best_diff is None:
        print(-1)
    else:
        print(1 + x // best_diff + int((x % best_diff) > 0))

T = int(input())
for _ in range(T):
    N, X = list(map(int, input().split()))
    A = -1
    B = -1
    for i in range(N):
        d, h = list(map(int, input().split()))
        A = max(A, d - h)
        B = max(B, d)
    
    if B >= X:
        print(1)
    elif A > 0:
        print((X - B + A - 1) // A + 1)
    else:
        print(-1)


import sys
input = sys.stdin.readline

T = int(input())
for testcases in range(T):
    n,x = list(map(int,input().split()))
    B=[tuple(map(int,input().split())) for i in range(n)]

    B0=max(B,key=lambda x:x[0]-x[1])
    dam=B0[0]-B0[1]
    BMAX=max(B)[0]



    if dam<=0 and x>BMAX:
        print(-1)
    elif BMAX>=x:
        print(1)
    else:
        print(1+max(0,-((x-BMAX)//(-dam))))


t = int(input())

for _ in [0]*t:
    n, heads = list(map(int, input().split()))
    attacks = [list(map(int, input().split())) for _ in range(n)]
    max_damage = max(attacks)[0]
    turn_damage = max(x-y for x, y in attacks)

    if heads > max_damage and turn_damage <= 0:
        print(-1)
        continue
    if heads <= max_damage:
        print(1)
        continue

    x = heads-max_damage
    print((x+turn_damage-1) // turn_damage + 1)


t = int(input())
for i in range(t):
	a = input().split(' ')
	n = int(a[1])
	m = 0
	eff = 0 
	for j in range(int(a[0])):
		b = input().split(' ')
		m = max(m,int(b[0]))
		eff = max(eff,int(b[0])-int(b[1]))
	n -= m
	if n > 0:
		if eff>0:
			print((n-1)//eff+2)
		else:
			print(-1)
	else: 
		print(1)

from math import ceil
for t in range(int(input())):
    a = []
    n,x = list(map(int,input().split()))
    for i in range(n):
        a.append(list(map(int,input().split())))
    max_di = a[0][0]
    max_damage = a[0][0] - a[0][1]
    for i in a:
        if i[0] > max_di:
            max_di = i[0]
        if i[0]-i[1] > max_damage:
            max_damage = i[0]-i[1]
    x -= max_di
    if x > 0:
        if max_damage <= 0:
            print(-1)
        else:
            print(ceil(x/max_damage)+1)
    else:
        print(1)





        


import sys
input = sys.stdin.readline
 
def getInt(): return int(input())
def getVars(): return list(map(int, input().split()))
def getList(): return list(map(int, input().split()))
def getStr(): return input().strip()
## -------------------------------
 
def addDictList(d, key, val):
    if key not in d: d[key] = []
    d[key].append(val)
 
def addDictInt(d, key, val):
    if key not in d: d[key] = 0
    d[key] = val
    
def addDictCount(d, key):
    if key not in d: d[key] = 0
    d[key] += 1
 
def addDictSum(d, key, val):
    if key not in d: d[key] = 0
    d[key] += val
 
## -------------------------------
 
t = getInt()
for _ in range(t):
    n, x = getVars()
    razn = 0
    maxD = 0
    for i in range(n):
        d, h = getVars()
        razn = max(razn, d-h)
        maxD = max(d, maxD)
    if razn == 0:
        if maxD < x:
            print(-1)
        else:
            print(1)        
    else:
        x = max(x-maxD, 0)
        if x == 0:
            print(1)
        else:
            res = x // razn
            if x == res*razn:
                print(res+1)
            else:
                print(res+2)
                


from collections import defaultdict as DD
from bisect import bisect_left as BL
from bisect import bisect_right as BR
from itertools import combinations as IC
from itertools import permutations as IP
from random import randint as RI
import sys
MOD=pow(10,9)+7

def IN(f=0):
    if f==0:
        return ( [int(i) for i in sys.stdin.readline().split()] )
    else:
        return ( int(sys.stdin.readline()) )

tc=IN(1)
for _ in range(tc):
    n,x=IN()
    a=[]
    maxD=-1
    for i in range(n):
        f,y=IN()
        maxD=max(maxD,f)
        a.append(f-y)
    i=0
    a.sort(reverse=True)
    x=x-maxD
    if x<=0:
        print(1)
    else:
        if a[0]<=0:
            print(-1)
        else:
            r=x/a[0]
            if int(r)!=r:
                r = int(r)+1
            print(int(r+1))
        


t=int(input())
for _ in range(t):
    n,xx=list(map(int,input().split()))
    #print(n,xx)
    it=[]
    for __ in range(n):
        it.append(list(map(int,input().split())))
    x=max(it,key=lambda a:a[0]-a[1])
    r=x[0]-x[1]
    
    if r<=0:
        if max(it)[0]>=xx:
            print(1)
        else:
            print(-1)
        continue
    aa=max(it)[0]
    xx=max(0,xx-aa)
    
    tot=(xx/r)
    if tot%1!=0:
        tot=int(tot)+1
    else:
        tot=int(tot)
    print(tot+1)
    


def ii():
  return int(input())
def ss():
  return [x for x in input()]
def si():
  return [int(x) for x in input().split()]
def mi():
  return map(int, input().split())
def r(s):
  return s[0] - s[1]
t = ii()
for i in range(t):
  a, b = mi()
  s = [si() for i in range(a)]
  maxout = max(s, key = lambda x: x[0])[0]
  maxin = max(s, key = lambda x: x[0] - x[1])
  maxin = maxin[0] - maxin[1]
  if b <= maxout:
    print(1)
  elif maxin <= 0:
    print(-1)
  else:
    print((b - maxout - 1) // maxin + 2)

import math
t=int(input())
for _ in range(t):
    n,inithead=list(map(int,input().split()))
    dif=[]
    desl=[]
    for i in range(n):
        des,hinc=list(map(int,input().split()))
        dif+=[des-hinc]
        desl+=[des]
    maxdes=max(desl)
    maxdif=max(dif)
    if(maxdes<inithead and maxdif<=0):
        print(-1)
    else:
        count=1
        head=inithead-maxdes
        if(head>0):
            count+=math.ceil(head/maxdif)
        print(count)
        
    
         


import math
t=int(input())
f=[]
for i in range(t):
    n,x=map(int,input().split())
    max1=0
    max2=0
    for i in range(n):
        a,b=map(int,input().split())
        max1=max(max1,a)
        max2=max(max2,a-b)
    if max1>=x:
        f+=[1]
    else:
        if max2>0:
            f+=[1+math.ceil((x-max1)/max2)]
        else:
            f+=[-1]
for i in f:
    print(i)

'''input
3
3 10
6 3
8 2
1 4
4 10
4 1
3 2
2 6
1 100
2 15
10 11
14 100

'''
import sys
from collections import defaultdict as dd
from itertools import  permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
from  heapq import heappush as hpush
from heapq import heappop as hpop
mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())


for _ in range(ri(1)):
	n, curr = ri()
	a = []
	for i in range(n):
		a.append(ri())
	a.sort(key = lambda x: -x[0]+x[1])

	hey = a[0][0]-a[0][1]
	take=-1
	b=[]
	for i,j in a:
		take = max(take,i)
		b.append(i-j)
	b.sort(reverse =True)
	ans =0
	curr = curr -take
	if curr<=0:
		print(1)
	else:
		if b[0]<=0:
			print(-1)
		else:
			hey = curr//b[0]
			if curr%b[0] ==0:
				print(hey+1)
			else:
				print(hey+2)

	# if curr<= a[0][0]:
	# 	print(1)
	# 	continue
	# if hey<=0:
	# 	print(-1)
	# else:


	# 	now = curr//hey
	# 	if now==0:
	# 		print(1)
	# 		continue
	# 	now -=1
	# 	rem = curr - now*hey
	# 	ans =now
	# 	#print(now,rem)
	# 	while (rem>0):
	# 		rem -= a[0][0]
	# 		ans +=1
	# 		if rem<=0:
	# 			break
	# 		rem += a[0][1]
	# 	print(ans)


T = int(input())

while T > 0:
    T -= 1
    n, head = map(int, input().split())
    
    possible = False
    eff = 0
    maxDmg = 0
    for i in range(n):
        kill, respawn =  map(int, input().split())
        if kill > respawn:
            possible = True
        
        eff = max(eff, kill - respawn)
        maxDmg = max(maxDmg, kill)
    
    if maxDmg >= head:
        print(1)
    elif not possible:
        print(-1)
    else:
        print((head - maxDmg) // eff + (1 if (head - maxDmg) % eff else 0) + 1)

from bisect import bisect_left as bl
from collections import defaultdict as dd


for _ in range(int(input())):
	n, x = [int(i) for i in input().split()]
	l = []
	f = dd(int)
	for j in range(n):
		d, h = [int(i) for i in input().split()]
		l.append(d - h)
		f[d] = 1
	#print(n, x)
	l.sort(reverse = 1)
	#print(l)
	ans = 1
	x -= max(f.keys())
	if x <= 0:
		print(ans)
	else:
		if l[0] <= 0:
			ans = -1
		else:
			ans = x // l[0]
			if (x % l[0]) == 0:
				ans += 1
			else:
				ans += 2
		print(ans)

t = int(input())
for _ in range(t):
    n, x = list(map(int, input().split()))
    b = [tuple(map(int, input().split())) for i in range(n)]
    shot_gun = b[0]
    uzi = b[0]
    for blow in b:
        if blow[0] > shot_gun[0]:
            shot_gun = blow
        if blow[0] - blow[1] > uzi[0] - uzi[1]:
            uzi = blow
    ans = None
    if shot_gun[0] >= x:
        ans = 1
    elif uzi[0] <= uzi[1]:
        ans = -1
    else:
        ans = 1 + (x-shot_gun[0]+uzi[0]-uzi[1]-1) // (uzi[0]-uzi[1])
    print (ans)