Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02995 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)

def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

a, b, c, d = map(int, input().split())
divc = b // c - a // c
if a % c == 0:
    divc += 1
divd = b // d - a // d
if a % d == 0:
    divd += 1
    
lcm = c * d // gcd(c, d)
divlcm = b // lcm - a // lcm
if a % lcm == 0:
    divlcm += 1


div_or = divc + divd - divlcm
print(int(b - a + 1 - div_or))

Buggy submission (verdict: Runtime Error):
import math

a, b, c, d = map(int, input().split())
divc = b // c - a // c
if a % c == 0:
    divc += 1
divd = b // d - a // d
if a % d == 0:
    divd += 1
    
lcm = c * d / math.gcd(c, d)
divlcm = b // lcm - a // lcm
if a % lcm == 0:
    divlcm += 1


div_or = divc + divd - divlcm
print(int(b - a + 1 - div_or))
Problem p03006 (python)

Fixed submission:
import itertools
from collections import defaultdict

n = int(input())
xy = []
for _ in range(n):
    xy.append(list(map(int, input().split())))
    
dd = defaultdict(int)
for lst in itertools.combinations(xy, 2):
    dx = lst[0][0] - lst[1][0]
    dy = lst[0][1] - lst[1][1]
    dd[(dx, dy)] += 1
    dd[(-dx, -dy)] += 1
ans = 0
for i, j in dd.items():
    ans = max(ans, j)
print(n - ans)

Buggy submission (verdict: Runtime Error):
4
1 1
1 2
2 1
2 2
Problem p03049 (python)

Fixed submission:
n = int(input())

a_end = 0
b_start = 0
a_b = 0
cnt = 0

for _ in range(n):
    s = input()
    cnt += s.count("AB")
    if s[0] == "B" and s[-1] == "A":
        a_b += 1
        continue
    if s[0] == "B":
        b_start += 1
    if s[-1] == "A":
        a_end += 1

if a_end == 0 and b_start == 0:
    tmp = max(a_b - 1, 0)
else:
    tmp = min(a_end,  b_start) + a_b
print(cnt + tmp)

Buggy submission (verdict: Runtime Error):
n = int(input())

a_end = 0
b_start = 0
a_b = 0
cnt = 0

for _ in range(n):
    s = input()
    cnt += s.count("AB")
    if s[0] == "B" and s[-1] == "A":
        a_b += 1
        continue
    if s[0] == "B":
        b_start += 1
    if s[-1] == "A":
        a_end += 1

if a_end == 0 and b_start == 0:
    tmp = max(a_b - 1, 0)
else:
    tmp = min(a_end + b_start) + a_b
print(cnt + tmp)
Problem p03274 (python)

Fixed submission:
n, k = map(int, input().split())
xlst = list(map(int, input().split()))
minus = []
plus = []
for x in xlst:
    if x < 0:
        minus.append(-1 * x)
    elif x > 0:
        plus.append(x)
    else:
        k -= 1
if k == 0:
    print(0)
    exit()
minus.append(0)
minus = minus[::-1]
plus = [0] + plus
ans = 10 ** 20
ml = len(minus)
pl = len(plus)

pos = min(k, ml - 1)
while 1:
    mm = minus[pos]
    pp = plus[k - pos]
    ans_tmp = max(mm, pp) + min(mm, pp) * 2
    ans = min(ans, ans_tmp)
    pos -= 1
    if pos == -1 or k - pos == pl:
        break
print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
xlst = list(map(int, input().split()))
minus = []
plus = []
for x in xlst:
    if x < 0:
        minus.append(-1 * x)
    elif x > 0:
        plus.append(x)
    else:
        k -= 1
if k == 0:
    print(0)
    exit()
minus.append(0)
minus = minus[::-1]
plus = [0] + plus
ans = 10 ** 20
ml = len(minus)
pl = len(plus)

pos = min(k, ml)
while 1:
    mm = minus[pos - 1]
    pp = plus[k - pos + 1]
    ans_tmp = max(mm, pp) + min(mm, pp) * 2
    ans = min(ans, ans_tmp)
    pos -= 1
    if pos == 0 or k - pos + 1 == pl:
        break
print(ans)
Problem p03280 (python)

Fixed submission:
a,b=map(int,input().split())
print((a-1)*(b-1))

Buggy submission (verdict: Runtime Error):
n,m,q=map(int,input().split())
alist=[]
for i in range(m):
    l,r=map(int,input().split())
    alist.append([l,r])
alist.sort()
for t in range(q):
    count=0
    blist=[]
    p,q=map(int,input().split())
    for j in range (len(alist)):
        if p<=alist[0][0]:
            alist.sort(key=lambda x:x[1])
            break
        blist.append(alist[0])
        alist.remove(alist[0])
    for j in range (len(alist)):
        if q>=alist[j][1]:
            count+=1
        else:
            break
    for k in blist:
        alist.append(k)
    print(count)
    alist.sort(key=lambda x:x[0])
Problem p03283 (python)

Fixed submission:
n, m, Q = map(int, input().split())
lr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    lr[l][r] += 1

rui = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        rui[i][j] = lr[i][j] + rui[i - 1][j] + rui[i][j - 1] - rui[i - 1][j - 1]
    
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    ans = rui[q][q] - rui[p][q] - rui[q][p] + rui[p][p]
    print(ans)

Buggy submission (verdict: Runtime Error):
n,m,q=map(int,input().split())
alist=[]
for i in range(m):
    l,r=map(int,input().split())
    alist.append([l,r])
alist.sort()
for t in range(q):
    count=0
    blist=[]
    p,q=map(int,input().split())
    for j in range (len(alist)):
        if p<=alist[0][0]:
            alist.sort(key=lambda x:x[1])
            break
        alist.remove(alist[0])
        blist.append(alist[0])
    for j in range (len(alist)):
        if q>=alist[j][1]:
            count+=1
        else:
            break
    for k in blist:
        alist.append(k)
    print(count)
Problem p03331 (python)

Fixed submission:
n = input()
ans = 0
for num in n:
    ans += int(num)
if ans == 1:
    ans = 10
print(ans)

Buggy submission (verdict: Runtime Error):
n = input()
num = 0
for num in n:
    ans += int(num)
if ans == 1:
    ans = 10
print(ans)
Problem p03352 (python)

Fixed submission:
x=int(input())
def beki(n):
    for i in range(2,32):
        k=n
        if k%i==0:
            t=0
            while k>=1:
                k/=i
                if k==1 and t>=1:
                    return True
                t+=1
y=1
for i in range (1,x+1):
    if beki(i)==True:
        y=i
print(y)

Buggy submission (verdict: Runtime Error):
x=int(input())
def beki(n):
    for i in range(2,10000):
        if n%i==0:
            t=
            while n>=1:
                n/=i
                if n==1 and t>=1:
                    return True
                if n<1:
                    return False
                t+=1
y=1
for i in range (1,x+1):
    if beki(i)==True:
        y=i
print(y)
Problem p03722 (python)

Fixed submission:
n, m = map(int, input().split())
g = []
for _ in range(m):
    a, b, c = map(int, input().split())
    g.append([a - 1, b - 1, -c])

def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    flg = False
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            inf_flg = d[-1]
            flg = True
    if flg:
        for i in range(n):
            update = False # 更新が行われたか
            for x, y, z in g:
                if d[y] > d[x] + z:
                    d[y] = d[x] + z
                    update = True
            if not update:
                break
            if i == n - 1:
                if inf_flg != d[-1]:
                    return "inf"
    return -1 * d[-1]

print(bellman_ford(0))

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
g = []
for _ in range(m):
    a, b, c = map(int, input().split())
    g.append([a - 1, b - 1, -c])

def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            inf_flg = d[-1]
            flg = True
    if flg:
        for i in range(n):
            update = False # 更新が行われたか
            for x, y, z in g:
                if d[y] > d[x] + z:
                    d[y] = d[x] + z
                    update = True
            if not update:
                break
            if i == n - 1:
                if inf_flg != d[-1]:
                    return "inf"
    return -1 * d[-1]

print(bellman_ford(0))
Problem p02536 (python)

Fixed submission:
import queue

N, M = map(int, input().split())
e = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    e[A].append(B)
    e[B].append(A)
# print(e)

seen = [-1] * N
k = -1
for i in range(N):
    if seen[i] == -1:
        k += 1
        seen[i] = k
        que = queue.Queue()
        que.put(i)
        while not que.empty():
            v = que.get()
            for nv in e[v]:
                if seen[nv] != -1: continue
                seen[nv] = k
                que.put(nv)
# print(seen)
print(k)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
e = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    e[A].append(B)
    e[B].append(A)
# print(e)

def dfs(n, k):
    seen[n] = k
    # print(seen)
    for i in e[n]:
        if seen[i] != -1: continue
        dfs(i, k)

seen = [-1] * N
k = -1
for i in range(N):
    if seen[i] == -1:
        k += 1
        dfs(i, k)
# print(seen)
print(k)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
e = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    e[A].append(B)
    e[B].append(A)
# print(e)

def dfs(n, k):
    seen[n] = k
    # print(seen)
    for i in e[n]:
        if seen[i] != -1: continue
        dfs(i, k)
    return

seen = [-1] * N
k = -1
for i in range(N):
    if seen[i] == -1:
        k += 1
        dfs(i, k)
# print(seen)
print(k)
Problem p02614 (python)

Fixed submission:
import numpy as np

H, W, K = map(int, input().split())
c = [[] for _ in range(H)]
for i in range(H):
    s = input()
    for j in s:
        if j == '.':
            c[i].append(0)
        else:
            c[i].append(1)

ans = 0
for bit in range(1 << (H+W)):
    red_array = np.full((H, W), False)
    cnt = 0
    for i in range(H+W):
        # print(bin(bit), i, bit>>i, bit>>i == 1, i<H, i-H)
        if (bit>>i)&1 == 1:
            if i < H:
                red_array[i,:] = True
            else:
                red_array[:,i-H] = True
    # print(bin(bit))
    # print(red_array)
    for y in range(H):
        for x in range(W):
            # print(bit, y, x, c[y][x], red_array[y,x],c[y][x] == 1 and not red_array[y, x])
            if c[y][x] == 1 and not red_array[y, x]:
                cnt += 1
    # print(cnt)
    if cnt == K:
        ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

H, W, K = map(int, input().split())
c = [[] for _ in range(H)]
for i in range(H):
    s = input()
    for j in s:
        if j == '.':
            c[i].append(0)
        else:
            c[i].append(1)

ans = 0
for bit in range(1 << (H+W)):
    red_array = np.full((H, W), False)
    cnt = 0
    for i in range(H+W):
        # print(bin(bit), i, bit>>i, bit>>i == 1, i<H, i-H)
        if (bit>>i)&1 == 1:
            if i < H:
                red_array[i,:] = True
            else:
                red_array[:,i-H] = True
    # print(bin(bit))
    # print(red_array)
    for y in range(H):
        for x in range(W):
            # print(bit, y, x, c[y][x], red_array[y,x],c[y][x] == 1 and not red_array[y, x])
            if c[y][x] == 1 and not red_array[y, x]:
                cnt += 1
    # print(cnt)
    if cnt == K:
        ans += 1
print(ans)
Problem p02690 (python)

Fixed submission:
X = int(input())
a = 1
flug = True
while flug:
    b = -119
    while b <= 118:
        if a ** 5 - b ** 5 == X:
            print(a, b)
            flug = False
            break
        else:
            b += 1
    a += 1

Buggy submission (verdict: Runtime Error):
X = int(input())
a = 1
while True:
    b = (a ** 5 - X) ** (1/5)
    if b.is_integer():
        b = int(b)
        break
    a += 1
print(a, b)
Problem p02720 (python)

Fixed submission:
import sys
K = int(input())
if K < 10:
    print(K)
    sys.exit()
lst = [[str(i)] for i in range(10)]
i = 9
while True:
    new_lst = [[] for j in range(10)]
    for j in range(10):     #0-9までについて
        for k in range(-1, 2):  #-1, 0, +1の3つについて
            if j == 0 and k == -1:
                continue
            if j == 9 and k == 1:
                break
            for l in lst[j+k]:
                tmp = str(j) + str(l)
                new_lst[j].append(tmp)
                # print(i, K , i == K)
                if j != 0:
                    i += 1
                    if i == K:
                        print(int(tmp))
                        sys.exit()
    # print(i, new_lst)
    lst = new_lst.copy()

Buggy submission (verdict: Runtime Error):
import sys
K = int(input())
if K < 10:
    print(K)
    sys.exit()
lst = [[str(i)] for i in range(10)]
i = 9
while True:
    new_lst = [[] for j in range(10)]
    for j in range(10):     #0-9までについて
        for k in range(-1, 2):  #-1, 0, +1の3つについて
            if j == 0 and k == -1:
                continue
            if j == 9 and k == 1:
                break
            for l in lst[j+k]:
                tmp = str(j) + str(l)
                new_lst[j].append(tmp)
                # print(i, K , i == K)
                if j != 0:
                    i += 1
                    if i == K:
                        print(int(tmp))
                        sys.exit()
    # print(i, new_lst)
    lst = new_lst.copy()
Problem p02727 (python)

Fixed submission:
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort()
q.sort()
r.sort()
red = []
green = []
less = []
for i in range(x):
    red.append(p[-i-1])
for i in range(y):
    green.append(q[-i-1])
# print(red, green)
for i in range(c):
    if len(red) > 0 and len(green) > 0:
        if red[-1] < green[-1]:
            if red[-1] < r[-i-1]:
                del red[-1]
                less.append(r[-i-1])
        else:
            if green[-1] <= r[-i-1]:
                del green[-1]
                less.append(r[-i-1])
    elif len(red) > 0:
        if red[-1] < r[-i-1]:
            del red[-1]
            less.append(r[-i-1])
    elif len(green) > 0:
        if green[-1] <= r[-i-1]:
            del green[-1]
            less.append(r[-i-1])
ans = sum(red) + sum(green) + sum(less)
# print(red, green, less)
print(ans)

Buggy submission (verdict: Runtime Error):
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort()
q.sort()
r.sort()
red = []
green = []
less = []
for i in range(x):
    red.append(p[-i-1])
for i in range(y):
    green.append(q[-i-1])
# print(red, green)
for i in range(c):
    if len(red) > 0:
        if red[-1] <= green[-1]:
            if red[-1] <= r[-i-1]:
                del red[-1]
                less.append(r[-i-1])
                continue
    if len(green) > 0:
        if red[-1] > green[-1]:
            if green[-1] <= r[-i-1]:
                del green[-1]
                less.append(r[-i-1])
ans = sum(red) + sum(green) + sum(less)
# print(red, green, less)
print(ans)

Buggy submission (verdict: Runtime Error):
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort()
q.sort()
r.sort()
red = []
green = []
less = []
for i in range(x):
    red.append(p[-i-1])
for i in range(y):
    green.append(q[-i-1])
# print(red, green)
for i in range(c):
    if red[-1] < green[-1]:
        if red[-1] <= r[-i-1]:
            del red[-1]
            less.append(r[-i-1])
    else:
        if green[-1] <= r[-i-1]:
            del green[-1]
            less.append(r[-i-1])
ans = sum(red) + sum(green) + sum(less)
# print(red, green, less)
print(ans)
Problem p02743 (python)

Fixed submission:
a, b, c = map(int, input().split())
if c - a - b > 0 and 4 * a * b < ((c - a - b) ** 2):
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
a, b, c = map(int, input().split())
if a + b + 2 * (a * b) ** 0.5 < c
    print("Yes")
else:
    print("No")
Problem p02582 (python)

Fixed submission:
weather = input()
rainy_count = 0
max_rainy_count = 0

for i in range(3):
  if weather[i] == "R":
    rainy_count += 1
    if max_rainy_count < rainy_count:
        max_rainy_count = rainy_count
    
  else:
    rainy_count = 0
            
print(max_rainy_count)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
p_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))
pc_list = []
max_score = -10**9

for m in range(n):
    score = 0
    num = p_list[m] - 1
    for l in range(k):
        score += c_list[num]
        num = p_list[num] - 1
        
        if score > max_score:
            max_score = score
 
print(max_score)
Problem p03611 (python)

Fixed submission:
import collections

n = int(input())
a_list = list(map(int, input().split()))
max_cnt = 0

c = collections.Counter(a_list)

for i in range(max(c.keys()) + 1) :
    cnt = c[i] + c[i + 1] + c[i + 2]
    
    if max_cnt < cnt :
        max_cnt = cnt

print(max_cnt)

Buggy submission (verdict: Runtime Error):
n = int(input())
a_list = list(map(int, input().split()))
s1 = len(a_list)
a_set = list(set(a_list))
s2 = len(a_set)
max_cnt = 0

if s1 == 1 :
    max_cnt = 1
elif s1 == 2 :
    if s2 == 1 :
        max_cnt = 2
    else :
        max_cnt = 1
else:
    cnt0 = a_list.count(a_set[0])
    cnt1 = a_list.count(a_set[1])
    
    for i in range(2, len(a_set)):
        cnt2 = a_list.count(a_set[i])
        cnt = cnt0 + cnt1 + cnt2
        
        if cnt > max_cnt :
            max_cnt = cnt
            
        cnt0 = cnt1
        cnt1 = cnt2

print(max_cnt)
Problem p02642 (python)

Fixed submission:
def main():

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

    d = dict()
    for v in A:
        d[v] = d.get(v, 0) + 1
    if 1 in d:
        if d[1] == 1: return 1
        else: return 0

    A = list(set(A))
    A.sort()
    s = set()
    ans = 0
    for i in range(len(A)):
        if d[A[i]] == 1:
            if A[i] not in s:
                ans += 1
        k = 1
        while k * A[i] <= A[-1]:
            s.add(k * A[i])
            k += 1

    return ans


if __name__ == '__main__':
    print(main())

Buggy submission (verdict: Runtime Error):
def main():

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

    d = dict()
    for v in A:
        d[v] = d.get(v, 0) + 1
    if 1 in d:
        if d[1] == 1: return 1
        else: return 0

    A = list(set(A))
    A.sort()
    s = set()
    ans = 0
    for i in range(N):
        if d[A[i]] == 1:
            if A[i] not in s:
                ans += 1
        k = 1
        while k * A[i] <= A[-1]:
            s.add(k * A[i])
            k += 1

    return ans




if __name__ == '__main__':
    print(main())
Problem p02744 (python)

Fixed submission:

def main():

    N = int(input())
    cur = [['a', set(['a'])]]
    for _ in range(N-1):
        temp = []
        for s, u in cur:
            for c in 'abcdefghij':
                 if c not in u:
                     temp.append([s + c, u | {c}])
                     break
                 else:
                    temp.append([s + c, u])
        cur = temp
    for s, _ in cur:
        print(s)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():

    H, W = map(int, input().split())
    ans = 0
    if W % 2 == 0 and H % 2 == 0:
        return (W//2) * (H//2) + (W//2) * (H//2)
    if W % 2 == 1 and H % 2 == 0:
        return ((W+1)//2) * (H//2) + (W//2) * (H//2)
    if W % 2 == 0 and H % 2 == 1:
        return (W//2) * ((H+1)//2) + (W//2) * (H//2)
    if W % 2 == 1 and H % 2 == 1:
        return ((W+1)//2) * ((H+1)//2) + (W//2) * (H//2)

if __name__ == '__main__':
    print(main())
Problem p02789 (python)

Fixed submission:
def main():

    N, M = map(int, input().split())
    if N == M:
        return "Yes"
    return "No"

if __name__ == '__main__':
    print(main())

Buggy submission (verdict: Runtime Error):
import math
import collections
def main():

    N = int(input())
    A = list(map(int, input().split()))
    mod = pow(10, 9) + 7

    def primes(n):
        b = [True] * (n//2)
        for i in range(3, int(n**0.5)+1, 2):
            if b[i//2]:
                b[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)

        return [2] + [2*i + 1 for i in range(1, n//2) if b]

    def isprime(n):
        if n == 1: return False
        for i in range(2, int(math.sqrt(n))+1):
            if n % i == 0:
                return False
        return True

    A = sorted(list(set(A)))
    N = len(A)

    ps = primes(int(math.sqrt(max(A))))

    d = dict()
    di = collections.defaultdict(dict)
    for i in range(N):
        if isprime(A[i]):
            if A[i] not in d:
                d[A[i]] = 1
            di[i][A[i]] = 1
        else:
            v = A[i]
            for p in ps:
                if p > v: break
                cnt = 0
                while v > 1 and v % p == 0:
                    cnt += 1
                    v //= p
                if p in d:
                    d[p] = max(d[p], cnt)
                else:
                    d[p] = cnt
                di[i][p] = cnt
            if v > 1:
                di[i][v] = 1
                if v not in d:
                    d[v] = 1

    ans = 0
    for i in range(N):
        b = 1
        for p in d:
            if p in di[i]:
                b *= pow(p, d[p]-di[i][p])
            else:
                b *= pow(p, d[p])
            b %= mod
        ans += b
        ans %= mod

    return ans

if __name__ == '__main__':
    print(main())
Problem p02883 (python)

Fixed submission:
def main():
 
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort(reverse = True)
    F.sort()
 
    if K >= sum(A): return 0
 
    B = [A[i] * F[i] for i in range(N)]
    l, r = 0, max(B)
    ans = float('inf')
    while l <= r:
        m = (l+r) // 2
        count = 0
        for i in range(N):
            if B[i] - m > 0:
                count += (B[i] - m) // F[i]
                if (B[i] - m) % F[i] != 0:
                    count += 1
        if count <= K:
            ans = min(ans, m)
            if r == m-1: break
            r = m-1
        else:
            if l == m+1: break
            l = m+1
        # print(l, r)
    return ans
 
if __name__ == '__main__':
    print(main())

Buggy submission (verdict: Runtime Error):
// g++ -std=c++14 submit.cpp
// #define INF 9223372036854775807

# include <bits/stdc++.h>
// # define INF 1e9 + 1
using namespace std;

int main(){
  long int N, K;
  cin >> N >> K;
  vector<long int> A, F;
  long int v;

  long int tot = 0;
  for(int i=0; i<N; i++){
    cin >> v;
    A.push_back(v);
    tot += v;
  }

  if(tot <= K){
    cout << 0 << endl;
    exit(0);
  }

  for(long int i=0; i<N; i++){
    cin >> v;
    F.push_back(v);
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  sort(F.begin(), F.end());

  long int l, r;
  l = 0;
  vector<long int> B;
  for(long int i=0; i<N; i++) {
    B.push_back(A[i] * F[i]);
    r = max(r, A[i]*F[i]);
  }

  long int ans = 1e12;

  while(l < r){
    long int m = (l+r) / 2;
    long int count = 0;
    for(long int i=0; i<N; i++){
      if(B[i] - m > 0){
        count += (B[i] - m) / F[i];
        if((B[i] - m) % F[i] != 0) count++;
      }
    }

    if(count <= K){
      ans = min(ans, m);
      if(r == m+1) break;
      r = m+1;
    } else {
      if(l == m-1) break;
      l = m-1;
    }
  }
  cout << ans << endl;

}