Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

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 H_{i} and the rate of growth of height as R_{i} 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 H_{i} and R_{i} 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 ≤ H_{i}, R_{i} ≤ 10^{9}$

------ Subtasks ------ 

$Subtask #1 [40 points]: 1 ≤  N, W, L ≤ 10^{4}$
$Subtask #2 [60 points]: No additional constraints$

----- Sample Input 1 ------ 
3 74 51

2 2

5 7

2 9
----- Sample Output 1 ------ 
7
----- explanation 1 ------ 
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.

Difficulty: MEDIUM_HARD
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
(n, w, l) = [int(i) for i in input().split(' ')]
h = [None] * n
r = [None] * n
for i in range(n):
	(h[i], r[i]) = [int(i) for i in input().split(' ')]
lo = 0
hi = 10 ** 30
ans = hi
while lo <= hi:
	mid = (lo + hi) // 2
	sum = 0
	for i in range(n):
		if h[i] + r[i] * mid >= l:
			sum += h[i] + r[i] * mid
	if sum >= w:
		ans = mid
		hi = mid - 1
	else:
		lo = mid + 1
print(ans)


(n, w, l) = map(int, input().split())
ht = [0] * n
rt = [0] * n
for i in range(n):
	(ht[i], rt[i]) = map(int, input().split())
left = 0
right = 10 ** 18 - 1
while left < right:
	mid = (left + right) // 2
	s = 0
	for i in range(n):
		val = ht[i] + mid * rt[i]
		if val >= l:
			s += val
	if s >= w:
		right = mid
	else:
		left = mid + 1
print(left)


def get_months():
	m = 1
	while True:
		h2 = [h + g * m for (h, g) in zip(height, growth)]
		if sum([h for h in h2 if h >= l]) >= w:
			break
		m *= 2
	if m == 1:
		return 1
	high = m
	low = m // 2
	while low < high:
		mid = (low + high) // 2
		h2 = [h + g * mid for (h, g) in zip(height, growth)]
		if sum([h for h in h2 if h >= l]) >= w:
			high = mid - 1
		else:
			low = mid + 1
	low2 = [h + g * (low - 1) for (h, g) in zip(height, growth)]
	if sum([h for h in low2 if h >= l]) >= w:
		low = low - 1
	else:
		low3 = [h + g * low for (h, g) in zip(height, growth)]
		low4 = [h + g * (low + 1) for (h, g) in zip(height, growth)]
		sum3 = sum([h for h in low3 if h >= l])
		sum4 = sum([h for h in low4 if h >= l])
		if sum3 < w and sum4 >= w:
			low = low + 1
	return low
(n, w, l) = (int(i) for i in input().split())
height = []
growth = []
for _ in range(n):
	(h, g) = (int(i) for i in input().split())
	height.append(h)
	growth.append(g)
wood = sum([h for h in height if h >= l])
if wood >= w:
	print(0)
else:
	print(get_months())


def valid(months):
	wood = 0
	for i in range(n):
		height = h[i] + r[i] * months
		if height >= l:
			wood += height
			if wood >= w:
				return True
	return False
(n, w, l) = map(int, input().split())
h = [0] * n
r = [0] * n
for i in range(n):
	(h[i], r[i]) = map(int, input().split())
low = mid = ans = 0
high = w // min(r)
while low <= high:
	mid = low + (high - low) // 2
	if valid(mid):
		ans = mid
		high = mid - 1
	else:
		low = mid + 1
print(ans)


(n, w, l) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
first = 0
last = 10 ** 18
while first <= last:
	mid = (first + last) // 2
	su = 0
	for i in range(n):
		s = a[i][0] + mid * a[i][1]
		if s >= l:
			su += s
	if su >= w:
		ans = mid
		last = mid - 1
	else:
		first = mid + 1
print(ans)


(n, w, l) = list(map(int, input().split()))
h = []
r = []
for i in range(n):
	(a, b) = list(map(int, input().split()))
	h.append(a)
	r.append(b)

def isValid(t):
	s = 0
	for i in range(n):
		if h[i] + r[i] * t >= l:
			s = s + h[i] + r[i] * t
			if s >= w:
				return True
	return False
lo = -1
hi = 10 ** 18 + 11
while hi - lo > 1:
	m = (lo + hi) // 2
	if isValid(m):
		hi = m
	else:
		lo = m
print(hi)


(n, w, l) = list(map(int, input().split()))
h = []
r = []
for i in range(n):
	(a, b) = list(map(int, input().split()))
	h.append(a)
	r.append(b)

def isValid(t):
	sum = 0
	for i in range(n):
		if h[i] + r[i] * t >= l:
			sum = sum + h[i] + r[i] * t
			if sum >= w:
				return True
	return False
low = -1
high = 10 ** 18 + 1
while high - low > 1:
	mid = (low + high) // 2
	if isValid(mid):
		high = mid
	else:
		low = mid
print(high)


(n, W, L) = map(int, input().split())
H = []
R = []
for _ in range(n):
	(p, q) = map(int, input().split())
	H.append(p)
	R.append(q)

def isValid(t):
	s = 0
	for i in range(n):
		l = H[i] + R[i] * t
		if l >= L:
			s += l
		if s >= W:
			return True
	return False
l = -1
h = 10 ** 18 + 1
while h - l > 1:
	m = (l + h) // 2
	if isValid(m):
		h = m
	else:
		l = m
print(h)


import math
(N, required_wood, min_cut_limit) = map(int, input().rstrip().split())
initial_height = []
rate_increase = []
for i in range(N):
	(a, b) = map(int, input().rstrip().split())
	initial_height.append(a)
	rate_increase.append(b)

def forest(N, initial_height, rate_increase, min_cut_limit, required_wood):
	required_months = []

	def check(mid):
		curr_sum = 0
		for i in range(N):
			temp = initial_height[i] + rate_increase[i] * mid
			if temp >= min_cut_limit:
				curr_sum += temp
			if curr_sum >= required_wood:
				return True
		return False
	end = -1
	for i in range(N):
		end = max(end, math.ceil((required_wood - initial_height[i]) / rate_increase[i]))
	start = 0
	if end == 0:
		return end
	result = end
	while start <= end:
		mid = start + (end - start) // 2
		if check(mid):
			result = mid
			end = mid - 1
		else:
			start = mid + 1
	return result
print(forest(N, initial_height, rate_increase, min_cut_limit, required_wood))


x = input()
inp = list(map(int, x.split(' ')))
(n, w, l) = (inp[0], inp[1], inp[2])
hr = []
for i in range(n):
	x = input()
	h_i = int(x.split(' ')[0])
	r_i = int(x.split(' ')[1])
	hr.append([h_i, r_i])

def search(left, right):
	if left > right:
		return left
	center = (left + right) // 2
	arr = [item[0] + center * item[1] for item in hr]
	valid_trees = [i for i in arr if i >= l]
	if sum(valid_trees) == w:
		return center
	elif sum(valid_trees) > w:
		return search(left, center - 1)
	else:
		return search(center + 1, right)
left = 0
right = 10 ** 18 + 1
print(search(left, right))


(n, w, l) = list(map(int, input().split()))
arr = list()
for i in range(n):
	arr.append(list(map(int, input().split())))

def can_cut(t_m):
	s = 0
	for t in arr:
		th = t[0] + t[1] * t_m
		if th >= l:
			s += th
	if s >= w:
		return True
	else:
		return False
t_L = -1
t_R = 1
while not can_cut(t_R):
	t_R *= 2
while t_R - t_L > 1:
	t_M = (t_L + t_R) // 2
	if can_cut(t_M):
		t_R = t_M
	else:
		t_L = t_M
print(int(t_R))


(n, w, l) = map(int, input().split())
h = []
r = []
for i in range(n):
	(hi, ri) = map(int, input().split())
	h.append(hi)
	r.append(ri)
low = -1
high = 10 ** 18
while high > low + 1:
	m = (low + high) // 2
	cnt = 0
	for i in range(n):
		req = h[i] + r[i] * m
		if req >= l:
			cnt += req
		if cnt >= w:
			break
	if cnt >= w:
		high = m
	else:
		low = m
print(high)


trees = []
n = 0
w = 0
l = 0

def check(m):
	wood = 0
	for i in range(n):
		h = trees[i][0] + trees[i][1] * m
		if h >= l:
			wood += h
	return wood >= w
(n, w, l) = map(int, input().split())
for _ in range(n):
	(i, j) = map(int, input().split())
	trees += [(i, j)]
low = 0
high = 10 ** 18 + 1
ans = 0
while low <= high:
	mid = low + (high - low) // 2
	if check(mid):
		ans = mid
		high = mid - 1
	else:
		low = mid + 1
print(ans)


arr = [int(i) for i in input().split()]
H = arr[-1]
W = arr[1]
h = []
r = []
for _ in range(arr[0]):
	arr = [int(i) for i in input().split()]
	h.append(arr[0])
	r.append(arr[1])
	arr = []

def ans(m):
	res = 0
	for i in range(len(h)):
		he = h[i] + r[i] * m
		if he >= H:
			res += he
		if res >= W:
			return True
	return False

def binarysearch():
	(low, high, res) = (-1, 10 ** 18 + 11, float('inf'))
	while high - low > 1:
		mid = low + high >> 1
		if ans(mid):
			res = min(res, mid)
			high = mid
		else:
			low = mid
	return res
print(binarysearch())


(n, w, l) = map(int, input().split())
(h, r) = ([], [])
(s, m1, m2) = (0, -1, -1)
for i in range(n):
	(hi, ri) = map(int, input().split())
	if hi >= l:
		s += hi
	y = (l - hi) // ri
	if m1 == -1 or y < m1:
		m1 = y
	h.append(hi)
	r.append(ri)
res = 0
if s >= w:
	print(0)
else:
	m2 = 10000000000000000000
	while m1 <= m2:
		s = 0
		m = (m1 + m2) // 2
		for i in range(n):
			x = h[i] + r[i] * m
			if x >= l:
				s += x
			if s >= w:
				break
		if s >= w:
			res = m
			m2 = m - 1
		else:
			m1 = m + 1
	print(res)


import math

def solve(ini, rate, N, W, min_val):
	total = 0
	low = 0
	high = int(math.pow(10, 18))
	while low <= high:
		mid = low + (high - low) // 2
		total = 0
		for j in range(N):
			Mon = rate[j] * mid + ini[j]
			if Mon >= min_val:
				total += Mon
			if total >= W:
				break
		if total < W:
			low = mid + 1
		else:
			high = mid - 1
	return low
(N, W, Min) = map(int, input().split())
i_l = []
R_l = []
for i in range(N):
	(a, b) = map(int, input().split())
	i_l.append(a)
	R_l.append(b)
ans = solve(i_l, R_l, N, W, Min)
print(ans)


from sys import stdout, stdin
from math import ceil, floor

def solve(x):
	temp = w
	for (h, r) in ls:
		ht = h + r * x
		if ht >= l:
			temp -= ht
			if temp <= 0:
				return True
	return False
(n, w, l) = map(int, stdin.readline().split())
ls = []
for _ in range(n):
	(h, r) = map(int, stdin.readline().split())
	ls.append((h, r))
(L, R) = (-1, 10 ** 18 + 1)
while R - L > 1:
	M = L + (R - L) // 2
	if solve(M):
		R = M
	else:
		L = M
print(R)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def can_cut(trees, time, l, w):
	tree_cut = 0
	for tree in trees:
		tree_len = tree[0] + time * tree[1]
		if tree_len >= l:
			tree_cut += tree_len
	return tree_cut >= w

def func():
	(n, w, l) = mul()
	trees = []
	for j in range(n):
		(h, r) = mul()
		trees.append([h, r])
	start = -1
	end = 10 ** 18
	while start + 1 < end:
		mid = (start + end) // 2
		if can_cut(trees, mid, l, w):
			end = mid
		else:
			start = mid
	return end
t = 1
for i in range(t):
	print(func())


(n, w, l) = map(int, input().split())
h = [0] * n
r = [0] * n
for i in range(n):
	(h[i], r[i]) = map(int, input().split())
(low, high) = (-1, 10 ** 18)
while high - low > 1:
	mid = (low + high) // 2

	def f(mid):
		total = 0
		for i in range(n):
			height = h[i] + mid * r[i]
			if height >= l:
				total += height
			if total >= w:
				return 1
		return 0
	if f(mid):
		high = mid
	else:
		low = mid
print(high)


(N, W, L) = map(int, input().split())
(h, r) = ([], [])
(s, t, c) = (0, -1, -1)
for i in range(N):
	(H, R) = map(int, input().split())
	if H >= L:
		s += H
	y = (L - H) // R
	if t == -1 or y < t:
		t = y
	if c == -1 or y > c:
		c = y
	h.append(H)
	r.append(R)
a = 0
if s >= W:
	print(0)
else:
	c = 10 ** 18
	while t <= c:
		s = 0
		m = (t + c) // 2
		for i in range(N):
			x = h[i] + r[i] * m
			if x >= L:
				s += x
			if s >= W:
				break
		if s >= W:
			a = m
			c = m - 1
		else:
			t = m + 1
	print(a)


(n, w, l) = map(int, input().split())
trees = []
for _ in range(n):
	(h, r) = map(int, input().split())
	trees.append((h, r))

def isitok(m):
	s = w
	for (h, r) in trees:
		height = h + r * m
		if height >= l:
			s -= height
		if s <= 0:
			return True
	return False
lo = 0
hi = 10 ** 18 + 11
ans = 10 ** 19
while lo <= hi:
	mid = (lo + hi) // 2
	if isitok(mid):
		hi = mid - 1
		ans = min(ans, mid)
	else:
		lo = mid + 1
print(ans)


(n, w, l) = map(int, input().split())
h = list()
r = list()
for i in range(n):
	(x, y) = map(int, input().split())
	h.append(x)
	r.append(y)

def valid(months):
	wood = 0
	for i in range(n):
		height = h[i] + r[i] * months
		if height >= l:
			wood += height
			if wood >= w:
				return True
	return False
low = mid = ans = 0
high = 10 ** 18
while low <= high:
	mid = low + (high - low) // 2
	if valid(mid):
		ans = mid
		high = mid - 1
	else:
		low = mid + 1
print(ans)


import math

def func(H, R, m, w, l):
	wood = 0
	for i in range(len(H)):
		if H[i] + R[i] * m >= l:
			wood += H[i] + R[i] * m
	if wood >= w:
		return True
	return False
(n, w, l) = map(int, input().split())
H = []
R = []
m = 0
for _ in range(n):
	(h, r) = map(int, input().split())
	if r:
		H.append(h)
		R.append(r)
		m = max(math.ceil((l - h) / r), math.ceil((w - h) / r), m)
left = 0
right = m + 1
ans = 0
while left <= right:
	if left == right:
		ans = left
		break
	if right == left + 1:
		if func(H, R, left, w, l):
			ans = left
			break
		else:
			ans = right
			break
	mid = left + (right - left) // 2
	if func(H, R, mid, w, l):
		right = mid
	else:
		left = mid + 1
print(ans)


import math

def isvalid(a, m, l, w):
	c = 0
	for i in a:
		if m * i[1] + i[0] >= l:
			c += m * i[1] + i[0]
	if c < w:
		return False
	else:
		return True
(n, w, l) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
e = -1
for i in a:
	e = max(e, math.ceil((w - i[0]) / i[1]))
s = 0
ans = -1
while s <= e:
	m = (s + e) // 2
	if isvalid(a, m, l, w):
		ans = m
		e = m - 1
	else:
		s = m + 1
print(ans)


(N, W, L) = map(int, input().rstrip().rsplit())
trees = [list(map(int, input().rstrip().rsplit())) for i in range(N)]
(l, r) = (-1, 10 ** 18)
while r - l > 1:
	mid = (l + r) // 2
	count = 0
	for i in trees:
		leng = i[0] + mid * i[1]
		if leng >= L:
			count += leng
	if count < W:
		l = mid
	else:
		r = mid
print(r)


def cut_poss(t, l, w, m):
	x = 0
	for i in range(len(t)):
		t_2 = t[i][0] + m * t[i][1]
		if t_2 >= l:
			x += t_2
	if x >= w:
		return True
	return False
(n, w, l) = map(int, input().split())
t_1 = []
for i in range(n):
	(a, b) = map(int, input().split())
	t_1.append([a, b])
t_r = 1
while cut_poss(t_1, l, w, t_r) != True:
	t_r *= 2
t_l = 0
while t_r > t_l:
	mid = t_l + (t_r - t_l) // 2
	if cut_poss(t_1, l, w, mid) == True:
		t_r = mid
	else:
		t_l = mid + 1
print(t_r)


(n, w, l) = map(int, input().split())
m = float('Inf')
v = []
for i in range(n):
	(a, b) = map(int, input().split())
	m = min(b, m)
	v.append((a, b))

def check(mid):
	s = 0
	for i in range(n):
		if v[i][0] + v[i][1] * mid >= l:
			s += v[i][0] + v[i][1] * mid
			if s >= w:
				return True
	return False
lo = 0
hi = w // m
res = 0
while lo <= hi:
	mid = (lo + hi) // 2
	if check(mid):
		hi = mid - 1
		res = mid
	else:
		lo = mid + 1
print(res)


def solve(l1, l2, x, y):
	s = 0
	for i in range(0, len(l1)):
		if l1[i] + x * l2[i] >= y:
			s += l1[i] + x * l2[i]
	return s
(n, w, l) = map(int, input().split())
v1 = []
v2 = []
for _ in range(n):
	(h, r) = map(int, input().split())
	v1.append(h)
	v2.append(r)
lo = 0
hi = 1000000000000000000
ans = 0
while lo <= hi:
	mid = lo + (hi - lo) // 2
	if solve(v1, v2, mid, l) >= w:
		hi = mid - 1
		ans = mid
	elif solve(v1, v2, mid, l) < w:
		lo = mid + 1
print(ans)


(n, w, l) = map(int, input().split())
(h, r) = ([], [])
for i in range(n):
	(u, v) = map(int, input().split())
	h.append(u)
	r.append(v)
(low, high) = (0, 10 ** 18)
while low < high:
	mid = (low + high) // 2
	sum_trees = 0
	for i in range(n):
		if h[i] + mid * r[i] >= l:
			sum_trees += h[i] + mid * r[i]
	if sum_trees >= w:
		high = mid
	else:
		low = mid + 1
print(low)


def getMaxWood(t):
	res = 0
	for i in range(N):
		if h[i] + r[i] * t >= L:
			res += h[i] + r[i] * t
	return res

def bs(i, j):
	if i > j:
		return i
	mid = (i + j) // 2
	t = getMaxWood(mid)
	if t == W:
		return mid
	if t > W:
		return bs(i, mid - 1)
	return bs(mid + 1, j)
(N, W, L) = list(map(int, input().split()))
h = [0 for i in range(N)]
r = [0 for i in range(N)]
for q in range(N):
	t = input().split()
	(h[q], r[q]) = (int(t[0]), int(t[1]))
print(bs(0, 10 ** 18 + 1))


(n, w, le) = list(map(int, input().split()))
a = [0] * n
r = [0] * n
for i in range(n):
	(u, v) = list(map(int, input().split()))
	a[i] = u
	r[i] = v
l = 0
h = int(1e+18) + 10
while l < h:
	mid = (l + h) // 2
	sum = 0
	for i in range(n):
		if a[i] + mid * r[i] >= le:
			sum += a[i] + mid * r[i]
	if sum >= w:
		h = mid
	else:
		l = mid + 1
print(l)


(n, w, l) = map(int, input().strip().split())
trees = []
for i in range(n):
	(h, s) = map(int, input().strip().split())
	trees.append((h, s))
L = 0
R = 10 ** 18 + 11
while L <= R:
	ans = 0
	M = L + R >> 1
	for (h, s) in trees:
		if h + s * M >= l:
			ans += h + s * M
		if ans > w:
			break
	if ans > w:
		R = M - 1
	elif ans < w:
		L = M + 1
	else:
		break
ans = 0
for (h, s) in trees:
	if h + s * M >= l:
		ans += h + s * M
if ans < w:
	M += 1
print(M)


(n, w, l) = map(int, input().split())
tr = []

def check(t):
	rem = w
	for (h, r) in tr:
		temp = h + r * t
		if temp >= l:
			rem -= temp
		if rem <= 0:
			return True
	return False

def solve():
	for it in range(n):
		(h, r) = map(int, input().split())
		tr.append((h, r))
	low = 0
	high = 10 ** 18
	ans = 0
	while low <= high:
		mid = low + high >> 1
		if check(mid):
			high = mid - 1
			ans = mid
		else:
			low = mid + 1
	print(ans)

def main():
	solve()
main()


def is_enough(heights, rates, w, l, cur_t):
	total = 0
	for i in range(len(rates)):
		cur_height = heights[i] + rates[i] * cur_t
		if cur_height >= l:
			total += cur_height
		if total >= w:
			return True
	return False
(n, w, l) = map(int, input().split())
(heights, rates) = ([0] * n, [0] * n)
for i in range(n):
	(heights[i], rates[i]) = map(int, input().split())
(high, low) = (10 ** 18, -1)
while high - low > 1:
	cur_m = (high + low) // 2
	if is_enough(heights, rates, w, l, cur_m):
		high = cur_m
	else:
		low = cur_m
print(high)


a = input().split()
N = int(a[0])
W = int(a[1])
L = int(a[2])
Harr = []
Rarr = []
for i in range(N):
	y = input().split()
	Harr.append(int(y[0]))
	Rarr.append(int(y[1]))

def check(mid):
	wood = 0
	for i in range(len(Harr)):
		h = Harr[i] + Rarr[i] * mid
		if h >= L:
			wood += h
	if wood >= W:
		return True
	return False
lo = 0
hi = 10 ** 18 + 1
while lo <= hi:
	mid = (lo + hi) // 2
	if check(mid):
		ans = 0
		ans += mid
		hi = mid - 1
	else:
		lo = mid + 1
print(ans)


(n, w, l) = map(int, input().split(' '))
h = []
r = []
for i in range(n):
	o = list(map(int, input().split(' ')))
	h.append(o[0])
	r.append(o[1])
(p, q) = (0, 10 ** 19)
while p <= q:
	m = (p + q) // 2
	sn = 0
	for j in range(n):
		if h[j] + r[j] * m >= l:
			sn += h[j] + r[j] * m
	if sn >= w:
		f = m
		q = m - 1
	else:
		p = m + 1
print(f)


def solve(x):
	temp = w
	for (h, r) in ls:
		ht = h + r * x
		if ht >= l:
			temp -= ht
			if temp <= 0:
				return True
	return False
(n, w, l) = map(int, input().split())
ls = []
for _ in range(n):
	(h, r) = map(int, input().split())
	ls.append((h, r))
(L, R) = (-1, 10 ** 18 + 1)
while R - L > 1:
	M = L + (R - L) // 2
	if solve(M):
		R = M
	else:
		L = M
print(R)


def fun(n, i, l, L):
	a = 0
	for _ in range(n):
		p = L[_][0] + i * L[_][1]
		a += p if p >= l else 0
	return a
x = input().split()
n = int(x[0])
w = int(x[1])
l = int(x[2])
L = []
for i in range(n):
	y = input().split()
	L.append([int(y[0]), int(y[1])])
(x, y) = (0, 10 ** 18)
ans = -1
while x <= y:
	mid = (x + y) // 2
	if fun(n, mid, l, L) >= w:
		ans = mid
		y = mid - 1
	else:
		x = mid + 1
print(ans)


(n, w, l) = map(int, input().split())
h = [0] * (n + 2)
r = [0] * (n + 2)
for i in range(1, n + 1):
	(h[i], r[i]) = map(int, input().split())

def get(t):
	res = 0
	for i in range(1, n + 1):
		if h[i] + r[i] * t >= l:
			res += h[i] + r[i] * t
	return res
ans = 1e+18
(lo, hi, mid) = (0, int(1e+18), 0)
while lo <= hi:
	mid = lo + (hi - lo) // 2
	if get(mid) >= w:
		hi = mid - 1
		ans = min(ans, mid)
	else:
		lo = mid + 1
print(ans)


(n, q, l) = map(int, input().split())
trees = []
for i in range(n):
	(h, s) = map(int, input().split())
	trees.append((h, s))

def good(t):
	remain = q
	for (h, s) in trees:
		height = h + s * t
		if height >= l:
			remain -= height
			if remain <= 0:
				return True
	return False
L = -1
R = 10 ** 18 + 11
while R - L > 1:
	M = L + R >> 1
	if good(M):
		R = M
	else:
		L = M
print(R)


def compute(h, r, w, l, mid):
	c = 0
	for i in range(len(h)):
		curr = h[i] + r[i] * mid
		if curr >= l:
			c += curr
	return c >= w
(n, w, l) = map(int, input().split())
(h, r) = ([], [])
for i in range(n):
	(a, b) = map(int, input().split())
	h.append(a)
	r.append(b)
(st, en) = (0, w)
while st < en:
	mid = (st + en) // 2
	if compute(h, r, w, l, mid):
		en = mid
	else:
		st = mid + 1
i = max(mid - 2, 0)
while not compute(h, r, w, l, i):
	i += 1
print(i)


import sys
input = sys.stdin.readline

def prod(months, l, harr, rarr):
	ret = 0
	for i in range(len(harr)):
		temp = harr[i] + rarr[i] * months
		if temp >= l:
			ret += temp
	return ret

def maxind(arr):
	max = -1
	ans = 0
	for i in range(len(arr)):
		if arr[i] > max:
			max = arr[i]
			ans = i
	return i
(n, w, l) = map(int, input().split(' '))
h_arr = []
r_arr = []
for i in range(n):
	(a, b) = input().split()
	h_arr.append(int(a))
	r_arr.append(int(b))
low = 0
high = 10 ** 19
mid = 0
ans = 10 ** 19
while low <= high:
	mid = (high + low) // 2
	temp = 0
	if prod(mid, l, h_arr, r_arr) >= w:
		high = mid - 1
		ans = mid
	else:
		low = mid + 1
print(ans)


(n, w, l) = list(map(int, input().split()))
h = []
r = []
for i in range(n):
	(p, q) = list(map(int, input().split()))
	h.append(p)
	r.append(q)

def isValid(t):
	s = 0
	for i in range(n):
		if h[i] + r[i] * t >= l:
			s = s + h[i] + r[i] * t
			if s >= w:
				return True
	return False
low = -1
high = 10 ** 18 + 11
while high - low > 1:
	mid = (low + high) // 2
	if isValid(mid):
		high = mid
	else:
		low = mid
print(high)


(n, w, l) = map(int, input().split())
a = []
for i in range(n):
	(h, r) = map(int, input().split())
	a.append([h, r])

def isgood(month):
	ans = 0
	for i in range(n):
		if a[i][0] + month * a[i][1] >= l:
			ans += a[i][0] + month * a[i][1]
		if ans >= w:
			return True
	return False
low = -1
high = 10 ** 18 + 1
while high - low > 1:
	mid = (low + high) // 2
	if isgood(mid) == True:
		high = mid
	else:
		low = mid
print(high)