This problem is given in two versions that differ only by constraints. If you can solve this problem in large constraints, then you can just write a single solution to the both versions. If you find the problem too difficult in large constraints, you can write solution to the simplified version only.

Waking up in the morning, Apollinaria decided to bake cookies. To bake one cookie, she needs n ingredients, and for each ingredient she knows the value a_{i} — how many grams of this ingredient one needs to bake a cookie. To prepare one cookie Apollinaria needs to use all n ingredients.

Apollinaria has b_{i} gram of the i-th ingredient. Also she has k grams of a magic powder. Each gram of magic powder can be turned to exactly 1 gram of any of the n ingredients and can be used for baking cookies.

Your task is to determine the maximum number of cookies, which Apollinaria is able to bake using the ingredients that she has and the magic powder.


-----Input-----

The first line of the input contains two positive integers n and k (1 ≤ n, k ≤ 1000) — 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} ≤ 1000), 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} ≤ 1000), 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
3 1
2 1 4
11 3 16

Output
4

Input
4 3
4 3 5 6
11 12 14 20

Output
3



-----Note-----

In the first sample it is profitably for Apollinaria to make the existing 1 gram of her magic powder to ingredient with the index 2, then Apollinaria will be able to bake 4 cookies.

In the second sample Apollinaria should turn 1 gram of magic powder to ingredient with the index 1 and 1 gram of magic powder to ingredient with the index 3. Then Apollinaria will be able to bake 3 cookies. The remaining 1 gram of the magic powder can be left, because it can't be used to increase the answer.

Difficulty: interview

Starter code:

Solutions:
n,k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
r = 0
ok = 1
while ok:
    L = [0 for _ in range(n)]
    for i in range(n):
        B[i] = B[i] - A[i]
        if B[i] < 0:
            L[i] = -B[i]
            B[i] = 0
    if sum(L) <= k:
        r += 1
        k = k - sum(L)
    else:
        ok = 0
print(r)
        


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 = 10**15
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if can_make(a, b, k, mid):
            lo = mid
        else:
            hi = mid

    print(lo)

main()


import sys

n, k = list(map(int, sys.stdin.readline().split()))
lst = list(map(int, sys.stdin.readline().split()))
ingr = list(map(int, sys.stdin.readline().split()))
ans = [[0,0,0] for i in range(n)]
for i in range(n):
    ans[i][0] = ingr[i]//lst[i]
    ans[i][1] = ingr[i]%lst[i]
    ans[i][2] = i
ans.sort(key = lambda x: [x[0],x[1]])
minn = ans[0][0]
while (k > 0):
    ans[0][1] += 1
    k -= 1
    if (ans[0][1] >= lst[ans[0][2]]):
        ans[0][0] += 1
        ans[0][1] = 0
    ans.sort(key = lambda x: [x[0],x[1]])
    if (ans[0][0] > minn):
        minn = ans[0][0]
print(minn)


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]
while k:
    cur = min(c)
    i = c.index(min(c))
    if k >= r[i]:
        k -= r[i]
        c[i] += 1
        r[i] = a[i]
    else: break
ans = min(c)
print(ans)


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])
cnt = mn
while k > 0:
    for i in range(n):
        if yes[i] // no[i] == mn:
            k -= no[i] * (mn + 1) - yes[i]
            yes[i] = no[i] * (mn + 1)
    if k >= 0:
        cnt += 1
        mn += 1
stdout.write(str(cnt))

# coding: utf-8

n, mp = list(map(int, input().split(" ")))
a_list = list(map(int, input().split(" ")))
b_list = list(map(int, input().split(" ")))

def bake(mp):
    minus = 0
    for i in range(n):
        b_list[i] -= a_list[i]
        if b_list[i] < 0:
            minus += b_list[i]
            b_list[i] = 0
    mp += minus
    if mp >= 0:
        return 1, mp
    else:
        return 0, mp

def init_bake():
    c = min([b // a for a, b in zip(a_list, b_list)])
    for i in range(n):
        b_list[i] -= a_list[i] * c
    return c

cookies = init_bake()
while True:
    c, mp = bake(mp)
    if c == 0:
        break
    cookies += c

print(cookies)


n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=[b[i]//a[i] for i in range(n)]
d=[b[i]%a[i] for i in range(n)]
while k:
    i=c.index(min(c))
    mi=min(k,a[i]-d[i])
    d[i]+=mi
    k-=mi
    c[i]+=d[i]//a[i]
    d[i]%=a[i]
print(min(c))

def main():
    def is_answer(ans):
        need = 0
        for i in range(n):
            need += max(0, a[i] * ans - b[i])
        return need <= k
    
    
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    left = 0
    right = 10 ** 18
    while (right - left > 1):
        middle = (left + right) // 2
        if (is_answer(middle)):
            left = middle
        else:
            right = middle
    print(left)
main()

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)


def bake(n, k, ai, bi):
    min_cookies = bi[0] // ai[0]
    for j in range(1, n):
        cookies = bi[j] // ai[j]
        if cookies < min_cookies:
            min_cookies = cookies
    possible = True
    while possible:
        cks = min_cookies + 1
        tenk = k
        for j in range(n):
            if bi[j] < (cks * ai[j]):
                tenk = tenk - ((cks * ai[j]) - bi[j])
                if tenk < 0:
                    possible = False
                    return min_cookies
        min_cookies = cks
    return min_cookies


def main():
    n, k = [int(i) for i in input().strip().split()]
    ai = [int(i) for i in input().strip().split()]
    bi = [int(i) for i in input().strip().split()]
    ans = bake(n, k, ai, bi)
    print(ans)

def __starting_point():
    main()


__starting_point()

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 True
	return False
	
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))

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

kol = [b[i] // a[i] for i in range(n)]
ost = [b[i] % a[i] for i in range(n)]

ans = min(kol)

check = True
while check:
    check = False
    for i in range(n):
        if kol[i] == ans:
            if k >= a[i] - ost[i]:
                k -= a[i] - ost[i]
                ost[i] = 0
                kol[i] += 1
                check = True

    if check:
        ans = min(kol)

print(ans)

def check():
    nonlocal n, k, A, B
    a = k
    h = 0
    for i in range(n):
        if k < 0:
            h = 1
            break
        else:
            if B[i] >= A[i]:
                B[i] -= A[i]
            else:
                if B[i] + k < A[i]:
                    h = 1
                    break
                else:
                    k -= (A[i] - B[i])
                    B[i] = 0

    if h == 1:
        return False
    else:
        return True
    
n, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
p = 0
while check():
    p += 1
print(p)

n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = [b[i]//a[i] for i in range(n)]
c1 = [b[i]%a[i] for i in range(n)]
while k>0:
    x = min(c)
    ind = c.index(x)
    b[ind]+=1
    k-=1
    c[ind] = b[ind]//a[ind]
    c1[ind] = b[ind]%a[ind]
print(min(c))


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
S = 0
_min = b[0] // a[0]
for i in range(n):
    S += a[i]
    x = b[i] // a[i]
    if x < _min:
        _min = x
for i in range(n):
    b[i] -= a[i] * _min
cnt = _min
while True:
    need = S
    for i in range(n):
        if b[i] < a[i]:
            need -= b[i]
            b[i] = 0
        else:
            need -= a[i]
            b[i] -= a[i]
    if need < k:
        k -= need
        cnt += 1
    elif need == k:
        cnt += 1
        break
    else:
        break
print(cnt)
        

    


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)



def minimum(l):
    min_value = l[0]
    min_index = 0
    for i in range(1, len(l)):
        if l[i] < min_value:
            min_value = l[i]
            min_index = i
    return min_value, min_index


n, k = [int(s) for s in input().split()]
needs = [int(s) for s in input().split()]
has = [int(s) for s in input().split()]
can_bake = [int(has[i] / needs[i]) for i in range(n)]
# print(can_bake)
while k > 0:
    min_value, min_index = minimum(can_bake)
    has[min_index] += 1
    k -= 1
    can_bake[min_index] = int(has[min_index] / needs[min_index])
print(min(can_bake))


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

results = [None] * n

for i in range(n):
    div, mod = b[i] // a[i], b[i] % a[i]
    insufficient = a[i] - mod
    results[i] = [div, mod, insufficient, i]


results.sort()

i = 0

while k > 0:
    k -= 1
    index = results[i][3]
    new_insufficient = results[i][2] - 1
    if new_insufficient == 0:
        results[i][0] += 1
        results[i][1] = 0
        results[i][2] = a[index]
    else:
        results[i][1] += 1
        results[i][2] -= 1
    results.sort()

print(results[0][0])



n, magic = list(map(int, input().split()))
gramNeed = list(map(int, input().split()))
gramHas = list(map(int, input().split()))

able = []
remain = []
for i in range(n):
    able.append([gramHas[i] // gramNeed[i], gramHas[i] % gramNeed[i], gramNeed[i]])
able.sort(key = lambda x: x[0])
ans = able[0][0]
for i in range(n):
    able[i][0] -= ans
while magic > 0:
    i = 0
    for i in range(n):
        if able[i][0] == 0:
            able[i][1] += 1
            magic -= 1
            if able[i][1] == able[i][2]:
                able[i][0] += 1
                able[i][1] = 0
            break
    if min(able, key = lambda x: x[0])[0] != 0:
        ans += 1
        for i in range(n):
            able[i][0] -= 1
print(ans)




"""
magic = 1
need =   2 1 4
has =   11 3 16
able =   2 0 1
remain = 1 0 0

ans = 3

magic = 3
need =   4 3  5  6
has =   11 15 14 20
able =   0 3  0  1
remain = 3 0  4  2
lack  =  1 3  1  4

ans = 2
"""


def main():
    from heapq import heapify, heappop, heappushpop
    n, k = list(map(int, input().split()))
    if n == 1:
        a, b = int(input()), int(input())
        print((b + k) // a)
        return
    l = list((b // a, a - (b % a), a) for a, b in zip(list(map(int, input().split())), list(map(int, input().split()))))
    heapify(l)
    b, r, a = heappop(l)
    while k >= r:
        k -= r
        b, r, a = heappushpop(l, (b + 1, a, a))
    print(b)


def __starting_point():
    main()

__starting_point()

import sys
a=[]
b=[]
l=0
val=0
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()]
while k>0:
    val=0
    for i in range(n):
        if a[i]<=b[i]:
            b[i]-=a[i]
        else:
            val=val+a[i]-b[i]
            b[i]=0
    if val<=k:
        l+=1
    k-=val
print(l)

def ok(x):
    need = sum([max(0, a[i] * x - b[i]) for i in range(n)])
    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)


import math

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


def if_sum_bigger(count):
    summ = 0
    for i in range(n):
        summ += max(0, count * req_ingr[i] - hvng_ingr[i])
    if summ <= k:
        return True
    else:
        return False

l = 0
r = 2 * (10 ** 9) + 1

while (r > l):
    m = math.floor((r + l) / 2)
    if if_sum_bigger(m):
        l = m + 1
    else:
        r = m
m = math.floor((r + l) / 2)
if if_sum_bigger(m):
    print(m)
else:
    print(m-1)


n, k = list(map(int, input().split()))
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [b[i] // a[i] for i in range(n)]
d = [b[i] % a[i] for i in range(n)]
while k:
        i = c.index(min(c))
        m = min(k, a[i]-d[i])
        d[i] += m
        k -= m
        c[i] += d[i]//a[i]
        d[i] %= a[i]
print(min(c))