The term of this problem is the same as the previous one, the only exception — increased restrictions.


-----Input-----

The first line contains two positive integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10^9) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where the i-th number is equal to the number of grams of the i-th ingredient, needed to bake one cookie.

The third line contains the sequence b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10^9), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.


-----Output-----

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.


-----Examples-----
Input
1 1000000000
1
1000000000

Output
2000000000

Input
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1

Output
0

Input
3 1
2 1 4
11 3 16

Output
4

Input
4 3
4 3 5 6
11 12 14 20

Output
3

Difficulty: interview

Starter code:

Solutions:
def can_make(a, b, k, n):
    k2 = k
    for t, v in zip(a, b):
        diff = v - t * n
        if diff < 0:
            k2 += diff

    return k2 >= 0

def main():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    lo = 0
    hi = 3 * 10**9
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if can_make(a, b, k, mid):
            lo = mid
        else:
            hi = mid

    print(lo)

main()


n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 0
r = int(1e10)
while r - l > 1:
    mid = (r + l) // 2
    fail = False
    kk = k
    for i in range(n):
        if b[i] < a[i] * mid:
            if kk > 0:
                kk -= a[i] * mid - b[i]
                if kk < 0:
                    fail = True
            else:
                fail = True
    if fail:
        r = mid
    else:
        l = mid
print(l)

def check(m):
    need = 0
    for ax, bx in zip(a, b):
        need += max(0, ax * m - bx)
    return need <= k

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

l = 0
r = 10 ** 10
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m
print(l)


from sys import stdin, stdout
n, k = map(int, stdin.readline().split())
no = list(map(int, stdin.readline().split()))
yes = list(map(int, stdin.readline().split()))
mn = float('inf')
for i in range(n):
    mn = min(mn, yes[i] // no[i])
l = mn
r = mn + k + 1
while r > l + 1:
    m = (l + r) // 2
    cnt = k
    for i in range(n):
        if yes[i] < no[i] * m:
            cnt -= no[i] * m - yes[i]
    if cnt >= 0:
        l = m
    else:
        r = m
stdout.write(str(l))

n,k = list(map(int, input().split()))
a = (list(map(int, input().split())))
b = (list(map(int, input().split())))
c = list(zip(a,b))
c.sort(key=lambda x:(x[1]//x[0]))
i = 0
count = c[0][1]//c[0][0]
part = 0
full = 0
while k>0 and i<n:
    if count < c[i][1]//c[i][0]:
        if k>part:
            k-=part
            part = 0
            count += 1
            dco = min(c[i][1]//c[i][0]-count, k//full)
            count += dco
            k -= dco*full
            part = full+c[i][0] - c[i][1]%c[i][0]
            full += c[i][0]
        else:
            break
    else:
        part += c[i][0] - c[i][1]%c[i][0]
        full += c[i][0]
    #~ print(part, full)
    i+=1
if k>part:
    count += 1
    k-=part
count += k//full
print(count)


n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

lo = 0
hi = 2*1e9

def p(cookies):
	powder = k
	for i in range(len(b)):
		have = b[i]
		one = a[i]
		remainder = have - (one * cookies)
		if remainder < 0:
			powder += remainder
			if powder < 0:
				return False
	return True
	
while lo < hi:
	m = (lo + hi) // 2
	if p(m):
		lo = m + 1
	else:
		hi = m
print(int(lo if p(lo) else lo - 1))

read = lambda: list(map(int, input().split()))
n, k = read()
a = list(read())
b = list(read())
c = [0] * n
r = [0] * n
for i in range(n):
    c[i] = b[i] // a[i]
    r[i] = a[i] - b[i] % a[i]

def f(x):
    k1 = k
    for i in range(n):
        if c[i] >= x:
            continue
        cnt = (x - c[i] - 1) * a[i] + r[i]
        k1 -= cnt
        if k1 < 0:
            return False
    return True
    
L, R = 0, 10 ** 10
while R - L > 1:
    M = (L + R) // 2
    if f(M): L = M
    else: R = M
ans = L
print(ans)


n, k = list(map(int, input().split()))

A = list(map(int, input().split()))
B = list(map(int, input().split()))

def Possible(x) :
    powder = k
    for i in range(n) :
        cnt = B[i] // A[i]
        if cnt < x:
            powder -= A[i]*x - B[i]
            if powder < 0 :
                return False
    return True

left = 0
right = 10**9 + 10**9 + 10

while left + 1 < right :
    mid = (left + right) // 2
    if Possible(mid) :
        left = mid
    else :
        right = mid

print(left)



n, k = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

x, y = 0, max(B) + k + 1
z = (x + y)//2
while z != x:
    credit = 0
    for i in range(n):
        credit += max(z*A[i] - B[i], 0)
    if credit > k:
        y = z
    else:
        x = z
    z = (x + y)//2
print(z)


# from duongtnhat's submission #17754492

def ok(u, a, b, n, k):
    for i in range(n):
        if b[i] >= a[i] * u:
            continue
        else:
            k -= a[i] * u - b[i]
            if k < 0:
                return False
    return k >= 0

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l, r = 0, 2000000010
while l < r - 1:
    g = (l + r) // 2
    if ok(g, a, b, n, k):
        l = g
    else:
        r = g
print(l)

def main():
    n, k = list(map(int, input().split()))
    l = sorted(((a, b) for a, b in zip(list(map(int, input().split())), list(map(int, input().split())))),
               key=lambda e: (e[1] // e[0], e[1] - e[0] % e[1]))
    lo, hi = l[0][1] // l[0][0], (l[-1][1] + k) // l[-1][0] + 1
    l.append((0, 1))
    while lo < hi - 1:
        mid, x = (lo + hi) // 2, k
        for a, b in l:
            a *= mid
            if a > b:
                x -= a - b
                if x < 0:
                    hi = mid
                    break
            else:
                lo = mid
                break
    print(lo)


def __starting_point():
    main()

__starting_point()

def ok(x):
    need = 0
    for i in range(n):
        tmp = a[i] * x - b[i]
        if tmp > 0:
            need += tmp
    return need <= k
n, k = (int(_) for _ in input().split())
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
lo, hi = 0, 2 * 10 ** 9
while lo <= hi:
    mid = (lo + hi) >> 1
    if ok(mid):
        lo = mid + 1
    else:
        hi = mid - 1
print(hi)


class Ingred:
    def __init__(self,i,a,b):
        self.index=i
        self.needed=a
        self.given=b
        self.possbl=int(b/a)
    def __repr__(self):
        return "["+str(self.needed)+","+str(self.given)+","+str(self.possbl)+"]"

def per(obj):
    return obj.possbl

def findIndex(x,arr):
    start=0
    end=len(arr)-1
    if arr[0].possbl>=x:
        return -1
    if arr[-1].possbl<x:
        #print("LAST HERE FOR " ,x)
        return end
    while True:
        ind=int((start+end)/2)
        if arr[ind].possbl<x:
            start=ind
            if ind<len(arr)-1 and arr[ind+1].possbl>=x:
                return ind
        else:
            end=ind

        if ind==len(arr)-1:
            #print("LAST HERE FOR " ,x)
            return ind
        
def xTimes(x,arr,needed,given,magic):
    ind=findIndex(x,arr)
    if ind==-1:
        return True
    deficit=needed[ind]*x-given[ind]
    #if x==178:
        #print(needed[ind],x,given[ind],deficit)
    if deficit>magic:
        return False
    return True
        
inf=list(map(int,input().split()))
n=inf[0]
k=inf[1]
temp=list(map(int,input().split()))
tmp=list(map(int,input().split()))
given=[0]*n
needed=[0]*n
array=[None]*n
for i in range(n):
    array[i]=Ingred(i,temp[i],tmp[i])
array=sorted(array,key=per)
for i in range(n):
    needed[i]=needed[i-1]+array[i].needed
    given[i]=given[i-1]+array[i].given
#print(array)
#print(needed)
#print(given)
start=0
end=4000000009
x=start
dic={}
while True:
    p=xTimes(x,array,needed,given,k)
    dic[x]=True
    if p:
        start=x
        #print("Possible for ",x," times.")
    else:
        end=x

    x=int((start+end)/2)
    try:
        dic[x]
        break
    except:
        damn=0
print(x)