forestga_36618
Chef is the head of commercial logging industry that recently bought a farm containing N trees. You are given initial height of the i-th tree by Hi and the rate of growth of height as Ri meters per month. For simplicity, you can assume that all the trees are perfect cylinders of equal radius. This allows us to consider only the height of trees when we talk about the amount of wood.


In Chef's country, laws don't allow one to cut a tree partially, so one has to cut the tree completely for gathering wood. Also, laws prohibit cutting trees of heights (strictly) lower than L meters.


Today Chef received an order of W meters (of height) of wood. Chef wants to deliver this order as soon as possible. Find out how minimum number of months he should wait after which he will able to fulfill the order. You can assume that Chef's company's sawing machines are very efficient and take negligible amount of time to cut the trees.


Input
There is a single test case per test file.
The first line of the input contains three space separated integers N, W and L denoting the number of trees in the farm, the amount of wood (in meters) that have to be gathered and the minimum allowed height of the tree to cut.
Each of next N lines contain two space separated integers denoting Hi and Ri respectively.

Output
Output a single integer denoting the number of months that have to pass before Chef will be able to fulfill the order.

Constraints

1 ≤ N ≤ 10^5
1 ≤ W, L ≤ 10^18
1 ≤ Hi, Ri ≤ 10^9


Example
Input:
3 74 51
2 2
5 7
2 9

Output:
7

Explanation
After 6 months, heights of each tree will be 14, 47 and 56 respectively. Chef is allowed to cut only the third tree, sadly it is not enough to fulfill an order of 74 meters of wood.
After 7 months, heights of each tree will be 16, 54 and 65 respectively. Now Chef is allowed to cut second and third trees. Cutting both of them would provide him 119 meters of wood, which is enough to fulfill the order.
def possible(x,l,w):
     sm=0
     for i in range(n):
          if((ini[i]+rate[i]*x)>=l):
               sm=sm+ini[i]+rate[i]*x
     if sm>=w:
          return 1
     else:
          return 0
n,w,l=map(int,raw_input().split())
ini=[]
rate=[]
for i in range(n):
     cur=map(int,raw_input().split())
     ini.append(cur[0])
     rate.append(cur[1])
low=0
high=100000000000000000099900
while low<=high:
     mid=(low+high)/2
     if(possible(mid,l,w)):
          high=mid-1
     else:
          low=mid+1
sm=0
for i in range(n):
     if((ini[i]+rate[i]*mid)>=l):
          sm=sm+ini[i]+rate[i]*mid
if(sm<w):
     mid=mid+1
print mid
3 74 51
2 2
5 7
2 9 3 74 82
2 2
5 7
2 9 3 74 51
3 2
5 7
2 9 3 51 141
2 2
1 7
2 9 3 62 82
2 2
1 7
1 4 3 74 51
3 2
5 7
2 3 3 74 30
2 2
1 7
2 12 3 93 82
0 2
7 7
2 9 3 74 30
2 2
1 7
2 18 3 51 113
0 2
2 7
2 9 1 74 0
3 2
5 7
2 5 1 70 82
2 2
0 2
3 7 2 70 82
2 4
0 2
3 7 3 62 82
4 4
1 6
1 2 3 28 35
4 2
1 1
1 18 3 57 14
0 2
3 12
6 9 3 108 82
0 4
1 6
1 2 3 108 82
0 4
1 3
1 2 1 5 -4
3 4
5 10
1 3 3 62 82
2 2
1 14
3 9 3 146 30
2 2
1 7
2 12 3 62 153
2 2
0 2
3 7 3 62 82
4 2
1 4
1 1 2 70 6
2 2
0 2
3 7 3 167 82
1 1
7 1
2 9 2 133 82
2 4
0 2
3 7 1 71 -2
3 2
5 7
2 3 2 123 82
4 4
-1 2
5 7 2 5 -4
3 3
5 10
1 4 3 167 5
1 1
7 1
2 9 1 74 -1
4 2
5 4
2 0 1 71 -2
3 1
5 19
2 3 3 253 158
2 1
14 3
3 9 2 123 82
8 4
-2 2
5 7 3 70 168
2 4
0 2
3 1 2 253 158
2 1
14 3
3 9 1 74 -3
1 3
5 11
0 2 2 369 89
2 1
14 3
3 13 1 108 155
-1 4
3 12
3 1 2 539 89
2 1
14 3
5 20 2 539 89
2 1
20 3
5 20 2 539 89
2 1
20 4
5 20 1 38 -4
0 1
1 1
-2 1 1 51 -4
0 1
1 1
-2 1 1 111 -2
1 1
-1 11
0 -1 1 83 -4
0 1
1 1
-2 1 1 111 -2
1 2
-1 11
0 -1 1 111 -2
1 3
-1 21
0 -1 1 110 -1
2 2
-1 72
-2 0 1 110 -1
-1 2
-2 72
-1 0 1 74 82
0 2
7 7
2 9 1 74 0
3 3
5 7
2 3 2 70 82
4 3
0 2
3 7 2 133 82
2 1
0 2
3 7 1 57 113
0 2
3 4
6 9 2 123 131
4 4
-1 2
5 7 1 138 51
6 2
5 7
2 5 2 74 21
4 2
1 1
2 6 3 74 82
2 2
1 7
2 9 3 51 82
2 2
1 7
2 9 3 62 82
2 2
1 7
2 9 3 62 82
2 2
1 7
3 9 3 62 82
2 2
1 7
1 9 3 74 82
0 2
5 7
2 9 3 74 82
2 2
1 7
2 12 3 62 82
4 2
1 7
2 9 3 62 82
2 2
1 2
3 9 3 74 82
0 2
7 7
2 9 3 51 141
0 2
1 7
2 9 3 62 82
2 2
0 2
3 9 3 62 82
2 2
1 7
1 1 3 74 51
3 2
5 7
2 5 3 51 141
0 2
2 7
2 9 3 62 82
2 2
0 2
3 7 3 62 82
4 2
1 7
1 1 3 74 0
3 2
5 7
2 5 3 93 82
0 2
7 13
2 9 3 74 30
2 2
1 7
0 18 3 70 82
2 2
0 2
3 7 3 62 82
4 2
1 7
1 2 3 93 82
0 1
7 13
2 9 3 74 30
4 2
1 7
0 18 3 51 113
0 2
2 7
3 9 3 62 82
4 2
1 10
1 2 1 74 0
3 2
5 7
2 3 3 167 82
0 1
7 13
2 9 3 74 30
4 2
1 7
1 18 3 51 113
0 2
3 7
3 9 2 70 82
2 2
0 2
3 7 3 62 82
4 4
1 10
1 2 1 74 -1
3 2
5 7
2 3 3 167 82
1 1
7 13
2 9 3 74 30
4 2
1 1
1 18 3 57 113
0 2
3 7
3 9 1 74 -2
3 2
5 7
2 3 3 167 82
2 1
7 13
2 9 3 74 35
4 2
1 1
1 18 3 57 113
0 2
3 7
6 9 2 70 82
4 4
0 2
3 7 3 62 82
1 4
1 6
1 2 1 74 -2
3 2
5 10
2 3
7
 9
 7
 16
 12
 10
 5
 11
 4
 13
 36
 40
 20
 14
 2
 3
 18
 27
 1
 6
 8
 22
 21
 17
 19
 33
 34
 30
 0
 15
 35
 68
 28
 29
 42
 80
 25
 89
 39
 131
 130
 104
 38
 51
 110
 83
 55
 37
 54
 56
 41
 24
 26
 67
 57
 32
 66
 23
 9
 9
 9
 9
 9
 9
 7
 9
 9
 9
 16
 9
 12
 10
 16
 12
 12
 5
 7
 5
 12
 12
 7
 5
 13
 9
 36
 9
 5
 13
 40
 9
 36
 9
 5
 13
 36
 9
 5
 12
 20
 14
 36
