Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

Appy loves balloons! She wants you to give her balloons on each of $N$ consecutive days (numbered $1$ through $N$); let's denote the number of balloons Appy wants on day $i$ by $A_{i}$. The problem is that you only have $M$ balloons. Fortunately, you can give her candies instead of balloons as well. On each day $i$, Appy accepts $B_{i}$ candies per each balloon you do not give her — formally, if you give Appy $X_{i}$ balloons on day $i$, then you have to give her $C_{i} = \mathrm{max}(0, A_{i} - X_{i}) \cdot B_{i}$ candies as well.

Your task is to minimize the maximum number of candies you give Appy on some day — find the minimum possible value of $\mathrm{max}(C_{1}, C_{2}, C_{3}, ..., C_{N})$.

------  Input ------
The first line of the input contains two space-separated integers $N$ and $M$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.
The third line contains $N$ space-separated integers $B_{1}, B_{2}, \dots, B_{N}$.

------  Output ------
Print a single line containing one integer — the minimum value of $\mathrm{max}(C_{1}, C_{2}, C_{3}, ..., C_{N})$.

------  Constraints  ------
$1 ≤ N ≤ 10^{5}$
$0 ≤ M ≤ 10^{18}$
$0 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
$0 ≤ B_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (27 points):
$1 ≤ A_{i} ≤ 10$ for each valid $i$
$1 ≤ B_{i} ≤ 10$ for each valid $i$

Subtask #2 (73 points): original constraints

----- Sample Input 1 ------ 
5 3 
1 2 3 4 5
1 2 3 4 5
----- Sample Output 1 ------ 
15
----- explanation 1 ------ 
If you give Appy $0, 0, 0, 1, 2$ balloons on days $1$ through $5$, then the required numbers of candies on each day are $1, 4, 9, 12, 15$. The maximum number of candies is $15$, required on day $5$.

Difficulty: MEDIUM_HARD
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
(N, M) = input().split()
(N, M) = (int(N), int(M))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
low = 0
high = A[0] * B[0]
for day in range(1, N):
	high = max(high, A[day] * B[day])
while low < high:
	mid = (low + high) // 2
	bal = 0
	for day in range(N):
		if B[day] != 0:
			bal += max(A[day] - mid // B[day], 0)
	if bal <= M:
		high = mid
	else:
		low = mid + 1
print(low)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
low = 0
totalNumBalloone = sum(a)
high = max(b) * (totalNumBalloone - m)
ans = -1

def possible(mid, a, b, n, m):
	sum = 0
	for i in range(n):
		sum += max(0, a[i] - mid // b[i])
		if sum > m:
			return False
	return True
while low <= high:
	mid = low + (high - low) // 2
	if possible(mid, a, b, n, m):
		ans = mid
		high = mid - 1
	else:
		low = mid + 1
print(ans)


def possible(max_candies, a, b, n, m):
	sum = 0
	for i in range(n):
		sum += max(0, a[i] - max_candies // b[i])
		if sum > m:
			return False
	return True

def solve(a, b, n, m):
	lo = 0
	sum = 0
	for i in range(n):
		sum += a[i]
	hi = max(b) * (sum - m)
	ans = -1
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if possible(mid, a, b, n, m):
			ans = mid
			hi = mid - 1
		else:
			lo = mid + 1
	return ans
(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
print(solve(a, b, n, m))


def snek1(z, n, m, b, c):
	ans = 0
	for i in range(n):
		x = b[i] - z // c[i]
		ans += max(0, x)
		if ans > m:
			return False
	return True

def snek2(n, m, b, c):
	l = 0
	r = 0
	for i in range(n):
		x = b[i] * c[i]
		if x > r:
			r = x
	ans = 0
	while l <= r:
		z = (l + r) // 2
		if snek1(z, n, m, b, c):
			ans = z
			r = z - 1
		else:
			l = z + 1
	return ans
(n, m) = map(int, input().split())
b = list(map(int, input().split()))
c = list(map(int, input().split()))
print(snek2(n, m, b, c))


def good(maxcan, n, m, balls, cand):
	cntballons = 0
	for i in range(n):
		ball_Onday = balls[i] - maxcan // cand[i]
		cntballons += max(0, ball_Onday)
		if cntballons > m:
			return False
	return True

def minCandiesAppy(n, m, balloons, candies):
	left = 0
	right = 0
	for i in range(n):
		temp = balloons[i] * candies[i]
		if temp > right:
			right = temp
	ans = 0
	while left <= right:
		mid = (left + right) // 2
		if good(mid, n, m, balloons, candies):
			ans = mid
			right = mid - 1
		else:
			left = mid + 1
	return ans
(n, m) = map(int, input().split())
balloons = list(map(int, input().split()))
candies = list(map(int, input().split()))
print(minCandiesAppy(n, m, balloons, candies))


import math
(N, M) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 0
h = a[0] * b[0]
for j in range(1, N):
	h = max(h, a[j] * b[j])
ans = h
while l <= h:
	mid = (l + h) // 2
	tot = 0
	for i in range(N):
		tot += max(0, a[i] - mid // b[i])
	if tot > M:
		l = mid + 1
	else:
		ans = mid
		h = mid - 1
print(ans)


def isvalid(a, b, m, mid):
	t = 0
	for i in range(len(a)):
		g = a[i] - mid // b[i]
		t += max(0, g)
		if t > m:
			return False
	return True
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
s = 0
e = 10 ** 18
ans = -1
while s <= e:
	mid = (s + e) // 2
	if isvalid(a, b, m, mid):
		ans = mid
		e = mid - 1
	else:
		s = mid + 1
print(int(ans))


(n, b) = map(int, input().split())
bal = list(map(int, input().split()))
can = list(map(int, input().split()))

def is_valid_total_candies(mid, bal, can, b):
	rem_bal = 0
	for i in range(len(bal)):
		if bal[i] * can[i] > mid:
			bal_mid = mid // can[i]
			rem_bal += bal[i] - bal_mid
		if rem_bal > b:
			return False
	return True
lo = 0
hi = 0
for i in range(n):
	if bal[i] * can[i] >= hi:
		hi = bal[i] * can[i]
while lo < hi:
	mid = lo + (hi - lo) // 2
	valid = is_valid_total_candies(mid, bal, can, b)
	if valid:
		hi = mid
	else:
		lo = mid + 1
print(lo)


def solve(l1, l2, k, ans, n):
	w = 0
	i = 0
	while i < n:
		if c[i] > ans:
			m = ans // b[i]
			w += a[i] - m
		if w > k:
			return 0
		i += 1
	return 1
(n, k) = (int(s) for s in input().split())
a = [int(s) for s in input().split()]
b = [int(s) for s in input().split()]
c = [a[i] * b[i] for i in range(n)]
low = 0
high = max(c)
while low < high:
	ans = (high + low) // 2
	if solve(a, b, k, ans, n):
		high = ans
	else:
		low = ans + 1
print(low)


from functools import reduce as rd
import operator as optr
import math
import itertools
inp = lambda : map(int, input().split())

def func(n, m, c):
	val = m
	i = len(c) - 1
	while i >= 0:
		if c[i][0] - n <= 0:
			i -= 1
			continue
		check = (c[i][0] - n) // c[i][1]
		if (c[i][0] - n) % c[i][1] > 0:
			check += 1
		val -= check
		if val < 0:
			return 0
		i -= 1
	return 1
(n, m) = inp()
l = list(inp())
add = sum(l)
b = list(inp())
a = []
for i in range(n):
	a.append(b[i] * l[i])
c = list(zip(a, b))
if add <= m:
	print(0)
else:
	c.sort()
	left = c[0][0]
	right = c[n - 1][0]
	(mid, flag) = (0, 0)
	while left <= right:
		mid = (left + right) // 2
		if func(mid, m, c) == 0:
			left = mid + 1
			flag = 0
		else:
			right = mid - 1
			flag = 1
	print(max(left, right))


(n, m) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = []
for i in range(0, len(A)):
	C.append(A[i] * B[i])
D = []
for (i, x) in sorted(zip(C, B)):
	D.append(x)
C.sort()
l = 0
h = max(C)
while l < h:
	b = 0
	mid = (h + l) // 2
	for i in range(len(C)):
		if C[i] <= mid:
			continue
		else:
			x = (C[i] - mid) // D[i]
			if C[i] - D[i] * x <= mid:
				b += x
			else:
				b += x + 1
	if b <= m:
		h = mid
	else:
		l = mid + 1
print(l)


def ans(a, b, n, m, mid, c):
	i = 0
	count = 0
	while i < n:
		if c[i] > mid:
			count += a[i] - mid // b[i]
		if m < count:
			return False
		i += 1
	return True
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
for i in range(n):
	c.append(a[i] * b[i])
low = 0
high = max(c)
mid = low + (high - low) // 2
while low < high:
	if ans(a, b, n, m, mid, c) == True:
		high = mid
	elif ans(a, b, n, m, mid, c) == False:
		low = mid + 1
	mid = low + (high - low) // 2
print(mid)


def check(A, B, maxCi, n, m):
	count = 0
	for day in range(n):
		wants = A[day]
		f = maxCi // B[day]
		if f > 0:
			atleast = max(0, wants - f)
			count += atleast
		else:
			count += wants
	return count <= m

def solve(A, B, m, n):
	(l, h) = (0, 10 ** 18)
	while l < h:
		ci = (l + h) // 2
		if check(A, B, ci, n, m):
			h = ci
		else:
			l = ci + 1
	return h
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = solve(A, B, m, n)
print(ans)


def bs(l, h):
	while l < h:
		m = (l + h) // 2
		if gf(m):
			h = m
		else:
			l = m + 1
	return l

def gf(x):
	d = c
	for i in range(n):
		d -= min(a[i], x // b[i])
	return d <= 0
(n, m) = map(int, input().split())
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))
c = sum(a)
c -= m
ind = 0
h = 0
for i in range(n):
	h = max(h, a[i] * b[i])
print(bs(0, h))


(n, m) = map(int, input().split())
ballons = list(map(int, input().split()))
candy = list(map(int, input().split()))
(low, high) = (0, 10 ** 18)

def check(val):
	add = 0
	for i in range(n):
		add += max(ballons[i] - val // candy[i], 0)
		if m < add:
			return False
	return True
while low <= high:
	mid = (low + high) // 2
	if check(mid):
		high = mid - 1
	else:
		low = mid + 1
print(low)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
(lo, hi) = (0, 0)
for i in range(n):
	hi += a[i] * b[i]

def check(mid):
	x = 0
	for i in range(n):
		x += max(a[i] - mid // b[i], 0)
	if x <= m:
		return True
	return False
while lo <= hi:
	mid = (lo + hi) // 2
	if check(mid):
		res = mid
		hi = mid - 1
	else:
		lo = mid + 1
print(res)


def check(mid):
	s = 0
	for i in range(n):
		curr = max(0, a[i] - mid // b[i])
		s += curr
	return s
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
low = 0
high = max(a) * max(b)
while low <= high:
	mid = (low + high) // 2
	val = check(mid)
	if val <= m:
		res = mid
		high = mid - 1
	else:
		low = mid + 1
print(res)


def balloons_needed(A, B, candies):
	c = 0
	for i in range(0, len(A)):
		if B[i] == 0:
			continue
		c += max(A[i] - candies // B[i], 0)
	return c
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
(l, r) = (0, 0)
for i in range(n):
	r = max(r, A[i] * B[i])
while l < r:
	mid = (l + r) // 2
	balloons = balloons_needed(A, B, mid)
	if balloons <= m:
		r = mid
	else:
		l = mid + 1
print(l)


def chk(mid, A, B, C, n, c):
	count = 0
	for i in range(n):
		if C[i] > mid:
			count += A[i] - mid // B[i]
	if count <= c:
		return True
	return False
for _ in range(1):
	(n, c) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = [A[i] * B[i] for i in range(0, n)]
	start = 0
	end = max(C)
	answer = -1
	while start <= end:
		mid = (start + end) // 2
		if chk(mid, A, B, C, n, c):
			answer = mid
			end = mid - 1
		else:
			start = mid + 1
	print(answer)


def succeed(mid, m):
	d = mid
	z = m
	k = 0
	for i in range(n):
		if a[i] * b[i] > d:
			v = a[i] * b[i] - d
			if v % b[i]:
				u = v // b[i] + 1
			else:
				u = v // b[i]
			z -= u
		if z < 0:
			k = 1
			break
	if k:
		return 0
	else:
		return 1

def bsea(l, r, m):
	while r - l > 1:
		mid = (l + r) // 2
		if succeed(mid, m):
			r = mid
		else:
			l = mid
	return r
(n, m) = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]
b = [int(x) for x in input().strip().split(' ')]
max = 0
s = 0
for i in range(n):
	s += a[i]
	if a[i] * b[i] > max:
		max = a[i] * b[i]
if s <= m:
	print(0)
else:
	l = 0
	r = max
	print(bsea(l, r, m))


def needm(c, k):
	need = 0
	for (a, b) in cs:
		buy = k // b
		if buy < a:
			need += a - buy
	return need
(n, m) = map(int, input().split())
ays = list(map(int, input().split()))
bs = list(map(int, input().split()))
if sum(ays) <= m:
	print(0)
else:
	cs = list(zip(ays, bs))
	hi = max((a * b for (a, b) in cs))
	lo = 0
	while hi - lo > 1:
		md = (hi + lo) // 2
		if needm(cs, md) > m:
			lo = md
		else:
			hi = md
	print(hi)


def balloons_needed(a, b, candies):
	need = 0
	for i in range(len(a)):
		if b[i] == 0:
			continue
		need += max(0, a[i] - candies // b[i])
	return need
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
r = 0
for i in range(n):
	r = max(r, a[i] * b[i])
l = 0
while l < r:
	mid = (l + r) // 2
	balloons = balloons_needed(a, b, mid)
	if balloons <= m:
		r = mid
	else:
		l = mid + 1
print(l)


(n, m) = map(int, input().split())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
lo = 0
hi = 10000000000000000000
while lo < hi:
	mid = (lo + hi) // 2
	now = 0
	for i in range(n):
		curr = max(0, l1[i] - mid // l2[i])
		now += curr
	if now <= m:
		hi = mid
	else:
		lo = mid + 1
print(lo)


import math
(n, m) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
k = 0
for i in range(n):
	k = max(k, a[i] * b[i])
low = 0
high = k
while low < high:
	mid = (low + high) // 2
	now = 0
	for i in range(n):
		curr = max(0, a[i] - mid // b[i])
		now += curr
	if now <= m:
		high = mid
	else:
		low = mid + 1
print(int(low))


from math import ceil

def binary(low, high, b, c, n, m):
	if low <= high:
		mid = (low + high) // 2
		val = 0
		for i in range(n):
			if c[i] > mid:
				if (c[i] - mid) % b[i] == 0:
					val += (c[i] - mid) // b[i]
				else:
					val += (c[i] - mid) // b[i] + 1
		if val <= m:
			low = binary(low, mid - 1, b, c, n, m)
		else:
			low = binary(mid + 1, high, b, c, n, m)
	return low

def extend_binary(b, c, n, m):
	return binary(0, max(c), b, c, n, m)
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [a[i] * b[i] for i in range(n)]
print(extend_binary(b, c, n, m))


import sys
import math
input = sys.stdin.readline
from collections import defaultdict
printf = sys.stdout.write
(n, m) = map(int, input().split())
balloons = list(map(int, input().split()))
candy = list(map(int, input().split()))
(l, r) = (0, max(map(lambda x, y: x * y, balloons, candy)))

def calc(candies):
	k = 0
	for i in range(n):
		if candy[i] == 0:
			continue
		k += max(balloons[i] - candies // candy[i], 0)
	return k
while l < r:
	mid = (l + r) // 2
	c = calc(mid)
	if c <= m:
		r = mid
	else:
		l = mid + 1
printf(str(l) + '\n')


def balloons(a, b, candy):
	total = 0
	for (ai, bi) in zip(a, b):
		if bi == 0:
			continue
		else:
			total += max(ai - candy // bi, 0)
	return total

def main():
	(n, m) = map(int, input().strip().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(left, right) = (0, max(a) * max(b))
	while left < right:
		mid = (left + right) // 2
		balloons_needed = balloons(a, b, mid)
		if balloons_needed <= m:
			right = mid
		else:
			left = mid + 1
	print(left)
main()


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [a[i] * b[i] for i in range(n)]
(lo, hi) = (0, 1000000000000000000)
import math
while lo < hi:
	mi = (lo + hi) // 2
	temp = 0
	for i in range(n):
		if mi <= c[i]:
			temp += (c[i] - mi) // b[i] + ((c[i] - mi) % b[i] > 0) * 1
	if temp > m:
		lo = mi + 1
	else:
		hi = mi
print((hi + lo) // 2)


t = input().split()
N = int(t[0])
M = int(t[1])
candies_list = []
balloon_list = []
balloons = input().split()
candies = input().split()
low = 0
mid = 0
max_val = 0
for i in range(N):
	balloon_list.append(int(balloons[i]))
for i in range(N):
	candies_list.append(int(candies[i]))
for i in range(N):
	cost = balloon_list[i] * candies_list[i]
	if cost > max_val:
		max_val = cost
high = max_val
while low < high:
	mid = (low + high) // 2
	bal_count = 0
	for i in range(N):
		bal_count += max(0, balloon_list[i] - mid // candies_list[i])
	if bal_count <= M:
		high = mid
	else:
		low = mid + 1
print(low)


import math
(n, m) = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
cost = [(A[i] * B[i], B[i]) for i in range(n)]

def is_pzbl(mi):
	req = 0
	for i in range(n - 1, -1, -1):
		if cost[i][0] <= mi or B[i] == 0:
			pass
		else:
			req += A[i] - mi // B[i]
	return req <= m
lo = 0
hi = 10 ** 19
while lo <= hi:
	mi = lo + hi >> 1
	if is_pzbl(mi):
		ans = mi
		hi = mi - 1
	else:
		lo = mi + 1
maxi = 0
for i in range(n):
	maxi = max(maxi, cost[i][0])
print(min(ans, maxi))


def satisfy(a, b, m, value):
	for i in range(n):
		candies = a[i] * b[i]
		if candies > value:
			if a[i] < value // b[i]:
				continue
			m -= a[i] - value // b[i]
			if m < 0:
				return False
	return True

def bsearch(a, b, m, value):
	lo = 0
	hi = value
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if satisfy(a, b, m, mid):
			hi = mid - 1
		else:
			lo = mid + 1
	return hi + 1
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
maximum = 0
for i in range(n):
	maximum = max(a[i] * b[i], maximum)
print(bsearch(a, b, m, maximum))


import math

def check(low, high):
	if high > low:
		mid = (high + low) // 2
		t = 0
		for i in range(n):
			if ab[i][1] > mid:
				t += ab[i][1] / ab[i][2] - mid // ab[i][2]
			else:
				break
		if t > m:
			return check(mid + 1, high)
		elif t <= m:
			return check(low, mid)
	else:
		return low
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if sum(a) <= m:
	print(0)
else:
	ab = list(zip(a, [a[i] * b[i] for i in range(n)], b))
	ab.sort(key=lambda x: x[1], reverse=True)
	print(check(1, ab[0][1]))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [a[i] * b[i] for i in range(n)]
ans = 0
lo = 0
hi = max(c)
while lo <= hi:
	mid = (lo + hi) // 2
	bal = 0
	for i in range(n):
		if b[i] == 0:
			continue
		bal += max(0, a[i] - mid // b[i])
	if bal <= m:
		ans = mid
		hi = mid - 1
	else:
		lo = mid + 1
print(ans)


def check(a, b, mid, m, n):
	temp = 0
	for i in range(n):
		if a[i] * b[i] > mid:
			temp += a[i] - mid // b[i]
		if m < temp:
			return 0
	return 1
(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
start = 0
end = start
for i in range(n):
	end = max(end, a[i] * b[i])
ans = 0
while start <= end:
	mid = (start + end) // 2
	if check(a, b, mid, m, n):
		end = mid - 1
		ans = mid
	else:
		start = mid + 1
print(ans)


(n, m) = [int(x) for x in input().split()]
(a, b) = ([], [])
(ma, mb) = (0, 0)
for x in input().split():
	a.append(int(x))
	if ma < int(x):
		ma = int(x)
for x in input().split():
	b.append(int(x))
	if mb < int(x):
		mb = int(x)
l = 0
r = ma * mb
while l <= r:
	mid = (r - l) // 2 + l
	k = 0
	for i in range(n):
		j = mid // b[i]
		k += max(0, a[i] - j)
	if k <= m:
		ans = mid
		r = mid - 1
	else:
		l = mid + 1
print(int(ans))


import math
(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
l = 0
r = max(a) * max(b)
while l <= r:
	mid = (r - l) // 2 + l
	k = 0
	for i in range(n):
		j = mid // b[i]
		k += max(0, a[i] - j)
	if k <= m:
		ans = mid
		r = mid - 1
	else:
		l = mid + 1
print(int(ans))


def bal_needed(a, b, candies):
	c = 0
	for i in range(len(a)):
		if b[i] == 0:
			continue
		c += max(a[i] - candies // b[i], 0)
	return c

def solve(a, b, n, m):
	(right, left) = (0, 0)
	for i in range(n):
		right = max(right, a[i] * b[i])
	while left < right:
		mid = (left + right) // 2
		bal = bal_needed(a, b, mid)
		if bal <= m:
			right = mid
		else:
			left = mid + 1
	return left
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(solve(a, b, n, m))


from math import ceil
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted([[a[i], b[i], a[i] * b[i]] for i in range(n)], key=lambda x: x[2])[::-1]
(l, r, t) = (0, c[0][2], -1)
while l < r:
	t = (l + r) // 2
	t1 = 0
	for i in range(n):
		if b[i] == 0:
			continue
		t1 += max(a[i] - t // b[i], 0)
	if t1 <= m:
		r = t
	else:
		l = t + 1
print(l)


def binary(l, r, baloons, B, P):
	if l <= r:
		mid = (l + r) // 2
		val = 0
		for i in range(len(P)):
			if P[i] > mid:
				if (P[i] - mid) % B[i] == 0:
					val = val + (P[i] - mid) // B[i]
				else:
					val = val + (P[i] - mid) // B[i] + 1
		if val > baloons:
			l = binary(mid + 1, r, baloons, B, P)
		else:
			l = binary(l, mid - 1, baloons, B, P)
	return l
n = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = A
D = B
P = []
for i in range(n[0]):
	P.append(A[i] * B[i])
c = n[1] // 2
k = c // 2
baloons = n[1]
print(binary(0, max(P), baloons, B, P))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [a[i] * b[i] for i in range(len(a))]
ans = 0
(l, r) = (0, max(c))
while l <= r:
	mid = (l + r) // 2
	bl = m
	flag = 1
	for i in range(len(c)):
		if c[i] - mid > 0:
			bl -= a[i] - mid // b[i]
		if bl < 0:
			flag = 0
			break
	if flag:
		r = mid - 1
		ans = mid
	else:
		l = mid + 1
print(ans)


def calc(mid, m, C):
	maxc = 0
	ballons = m
	for (c, a, b) in C:
		if c < mid:
			break
		ballons = ballons - (a - mid // b)
		maxc = max(mid // b * b, maxc)
	return (ballons, maxc)
(n, m) = map(int, input().split())
(A, B) = (list(map(int, input().split())), list(map(int, input().split())))
C = []
maxc = 0
for i in range(n):
	C.append((A[i] * B[i], A[i], B[i]))
C.sort(reverse=True)
beg = 0
end = C[0][0]
result = C[0][0]
while end > beg + 1:
	mid = (beg + end + 1) // 2
	(ballons, maxc) = calc(mid, m, C)
	if ballons < 0:
		beg = mid
	elif ballons > 0:
		end = mid
		result = maxc
	else:
		result = maxc
		break
print(result)


def check_least(n, m, a, b, c, least):
	required_m = 0
	for (index, ci) in enumerate(c):
		ai = a[index]
		bi = b[index]
		if ci > least:
			diff = ci - least
			required_m += diff // bi
			if diff % bi != 0:
				required_m += 1
		if required_m > m:
			return False
	return True

def binary_search(n, m, a, b, c, min_range, max_range):
	mid = (min_range + max_range) // 2
	possible = check_least(n, m, a, b, c, mid)
	if possible and min_range == max_range:
		return mid
	if possible:
		(min_range, max_range) = (min_range, mid)
	else:
		(min_range, max_range) = (mid + 1, max_range)
	return binary_search(n, m, a, b, c, min_range, max_range)

def solve(n, m, a, b, c):
	min_range = 0
	max_range = max(c)
	print(binary_search(n, m, a, b, c, min_range, max_range))
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [ai * bi for (ai, bi) in zip(a, b)]
solve(n, m, a, b, c)


from math import ceil

def binarySearch(c, l, r, b, m):
	if l <= r:
		mid = (l + r) // 2
		val = 0
		for i in range(len(c)):
			if c[i] > mid:
				if (c[i] - mid) % b[i] == 0:
					val += (c[i] - mid) // b[i]
				else:
					val += (c[i] - mid) // b[i] + 1
		if val <= m:
			l = binarySearch(c, l, mid - 1, b, m)
		else:
			l = binarySearch(c, mid + 1, r, b, m)
	return l
(n, m) = map(int, input().split())
a = [int(n) for n in input().split()]
b = [int(n) for n in input().split()]
c = []
for i in range(n):
	c.append(a[i] * b[i])
z = max(c)
if m == 0:
	print(z)
elif m >= sum(a):
	print(0)
else:
	if z < 10 ** 18:
		result = binarySearch(c, 0, z, b, m)
	else:
		result = binarySearch(c, 0, 10 ** 18, b, m)
	print(result)


def solve(low, high, b, c, n, m):
	if low <= high:
		mid = (low + high) // 2
		balloons = 0
		for i in range(n):
			if c[i] > mid:
				if (c[i] - mid) % b[i] == 0:
					balloons += (c[i] - mid) // b[i]
				else:
					balloons += (c[i] - mid) // b[i] + 1
		if balloons <= m:
			return solve(low, mid - 1, b, c, n, m)
		else:
			return solve(mid + 1, high, b, c, n, m)
	return low
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [a[i] * b[i] for i in range(n)]
print(solve(0, max(c), b, c, n, m))


def cond(n, m, a, b, x):
	y = 0
	for i in range(n):
		if a[i] * b[i] > x:
			y += a[i] - x // b[i]
			if y > m:
				return False
	return True

def binSearch(n, m, a, b, x):
	low = 0
	high = x
	r = x
	while low <= high:
		mid = (low + high) // 2
		if cond(n, m, a, b, mid):
			r = min(r, mid)
			high = mid - 1
		else:
			low = mid + 1
	return r
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = 0
for i in range(n):
	x = max(a[i] * b[i], x)
print(binSearch(n, m, a, b, x))


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
l = 0
h = 10 ** 18
while l <= h:
	midpoint = (l + h) // 2
	k = 0
	for i in range(n):
		j = midpoint // b[i]
		k += max(0, a[i] - j)
	if k <= m:
		output = midpoint
		h = midpoint - 1
	else:
		l = midpoint + 1
print(int(output))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted([[a[i] * b[i], b[i]] for i in range(n)], key=lambda x: x[0])

def find(i1, i2):
	if i1 > i2:
		return i1
	mid = (i1 + i2) // 2
	ss = m - sum([(i[0] - mid) // i[1] + (1 if (i[0] - mid) % i[1] else 0) for i in c if i[0] > mid])
	return find(mid + 1 if ss < 0 else i1, i2 if ss < 0 else mid - 1)
print(find(0, c[-1][0] + 1))


(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
(L, R) = (0, 10 ** 20)
while L < R:
	mid = (L + R) // 2
	temp = m
	for i in range(n):
		temp -= max(0, a[i] - mid // b[i])
	if temp < 0:
		L = mid + 1
	else:
		R = mid
print(L)


def find(A, B, N, M, k):
	for i in range(N):
		b = max(0, A[i] - k // B[i])
		M -= b
	return M >= 0

def binary(A, B, N, M):
	low = 0
	high = 10 ** 18
	while low < high:
		mid = (low + high) // 2
		if find(A, B, N, M, mid):
			high = mid
		else:
			low = mid + 1
	if find(A, B, N, M, mid):
		return mid
	else:
		return high
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
if M >= sum(A):
	ans = 0
elif M == 0:
	ans = 0
	for i in range(N):
		ans = max(ans, A[i] * B[i])
else:
	ans = binary(A, B, N, M)
print(ans)


from math import ceil
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list((A[i] * B[i] for i in range(N)))
upper_bound = max(C) + 1
lower_bound = -1
test_req = 0
while upper_bound - lower_bound > 1:
	balloon_dist = [ceil((C[i] - test_req) / B[i]) if C[i] > test_req else 0 for i in range(N)]
	balloons = sum(balloon_dist)
	if balloons == M:
		break
	if balloons > M:
		lower_bound = test_req
	if balloons < M:
		upper_bound = test_req
	test_req = (upper_bound - lower_bound) // 2 + lower_bound
else:
	balloon_dist = [ceil((C[i] - upper_bound) / B[i]) if C[i] > upper_bound else 0 for i in range(N)]
print(max((C[i] - balloon_dist[i] * B[i] for i in range(N))))


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

def check(N, M, A, B, C):
	total = 0
	for i in range(N):
		a = max(0, A[i] * B[i] - C)
		if a % B[i] == 0:
			total += a // B[i]
		else:
			total += a // B[i] + 1
		if total > M:
			return False
	return total <= M

def solve(N, M, A, B):
	(lo, hi) = (0, max([A[i] * B[i] for i in range(N)]))
	while lo < hi:
		maxc = lo + (hi - lo) // 2
		if check(N, M, A, B, maxc):
			hi = maxc
		else:
			lo = maxc + 1
	return lo
(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
print(solve(N, M, A, B))


def main():
	(N, BALLOONS) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	UPPER_BOUND = max([x * y for (x, y) in zip(A, B)]) + 1

	def predicate(MAX_TOFFEES_PER_DAY):
		required = 0
		for (ballons_req, toffees_per_ballon) in zip(A, B):
			LIM = min(ballons_req * toffees_per_ballon, MAX_TOFFEES_PER_DAY)
			in_exchange_of = LIM // toffees_per_ballon
			required += ballons_req - in_exchange_of
		return required <= BALLOONS

	def binary_search(low=0, high=UPPER_BOUND):
		while low < high:
			mid = low + (high - low) // 2
			if predicate(mid):
				high = mid
			else:
				low = mid + 1
		return low
	print(binary_search())
main()


def poss(k, inp, h):
	b = 0
	for i in range(0, len(inp)):
		el = inp[i]
		if el[1] == 0:
			continue
		elif k >= 0:
			v1 = el[0] - k
			v2 = el[1]
			chkval = int((v1 + v2 - 1) // v2)
			if chkval > 0:
				b += chkval
	if b <= h:
		return True
	else:
		return False

def solve(inp, h, t):
	low = 0
	high = t
	ans = t
	while low <= high:
		mid = (low + high) // 2
		if poss(mid, inp, h):
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
max_c = -1
s = 0
for i in range(0, n):
	tc = a[i] * b[i]
	s += a[i]
	c.append([tc, b[i]])
	if tc > max_c:
		max_c = tc
if m >= s:
	print(0)
else:
	minc = solve(c, m, max_c)
	print(minc)


I = lambda : map(int, input().split())

def C(a, b):
	return [a // b + 1, a // b][a % b == 0]

def f(d, k):
	return sum(((d[i][0] > k) * min(C(d[i][0] - k, d[i][1]), d[i][2]) for i in range(len(d))))
(n, m) = I()
a = list(I())
b = list(I())
d = []
l = 0
for i in range(n):
	d.append([a[i] * b[i], b[i], a[i]])
	l = max(l, d[i][0])
x = 0
while x != l:
	k = (x + l) // 2
	if f(d, k) > m:
		x = k + 1
	else:
		l = k
print(l)


import math as ma
import sys
from sys import exit
from decimal import Decimal as dec
from itertools import permutations

def li():
	return list(map(int, input().split()))

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def num():
	return map(int, input().split())

def nu():
	return int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
(n, m) = num()
a = li()
b = li()
z = []
for i in range(n):
	z.append((a[i] * b[i], i))
z.sort()
lo = 0
hi = max(z)[0]
while lo <= hi:
	mid = (lo + hi) // 2
	ss = 0
	for i in range(n):
		if z[i][0] <= mid:
			continue
		if (z[i][0] - mid) % b[z[i][1]] == 0:
			ss += (z[i][0] - mid) // b[z[i][1]]
		else:
			ss += (z[i][0] - mid) // b[z[i][1]] + 1
	if ss > m:
		lo = mid + 1
	else:
		hi = mid - 1
print(max(0, lo))


import math

def graph():
	res = 0
	d.clear()
	for i in range(n):
		if c[i] > mid:
			res += math.ceil((c[i] - mid) / b[i])
			d.append(c[i] - math.ceil((c[i] - mid) / b[i]) * b[i])
		else:
			d.append(c[i])
	if k == res:
		return 0
	if k > res:
		return 1
	if k < res:
		return 2
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = [int(x) for x in input().split()]
c = [x * y for (x, y) in zip(a, b)]
d = []
maxx = max(c)
minn = 0
ans = 0
while maxx >= minn:
	mid = (maxx + minn) // 2
	flag = graph()
	if flag == 0:
		ans = max(d)
		break
	elif flag == 1:
		ans = max(d)
		maxx = mid - 1
	else:
		minn = mid + 1
print(ans)


import math

def get_baloons_required(line):
	(baloons, max_h) = (0, 0)
	for (product, a, r) in arr3:
		if product > line:
			max_h = max(max_h, product - math.ceil((product - line) / r) * r)
			baloons += math.ceil((product - line) / r)
		else:
			max_h = max(max_h, product)
			break
	return (baloons, max_h)
(n, given_baloons) = map(int, input().split())
array1 = map(int, input().split())
array2 = map(int, input().split())
arr3 = [(a * b, a, b) for (a, b) in zip(array1, array2)]
arr3.sort(reverse=True)
upper_limit = arr3[0][0]
(lower, answer) = (0, arr3[0][0])
if given_baloons > 0:
	while lower <= upper_limit:
		mid_line = (lower + upper_limit) // 2
		(a, max_h) = get_baloons_required(mid_line)
		if a <= given_baloons:
			answer = max_h
		if a > given_baloons:
			lower = mid_line + 1
		elif a < given_baloons:
			upper_limit = mid_line - 1
		else:
			break
print(answer)


def b_search(N, M, a, b):
	low = 1
	high = max(a) * max(b)
	while low < high:
		mid = low + (high - low) // 2
		bn = 0
		for x in range(N):
			bn += max(0, a[x] - mid // b[x])
		if bn <= M:
			high = mid
		else:
			low = mid + 1
	return low
[N, M] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
print(b_search(N, M, a, b))