Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
 
tmp = 1
for num in A:
    tmp *= num
    if tmp > 1e18:
      break
  
if tmp <= 1e18:
    print(tmp)
elif 0 in tmp:
    print(0)
else:
    print(-1)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
 
tmp = 1
for num in A:
    tmp *= num
    if tmp > 1e18:
      break
  
if tmp <= 1e18:
    print(tmp)
elif 0 in A:
    print(0)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

tmp = 1
for num in A:
    tmp *= num
if tmp <= 1e18:
    print(tmp)
else:
    print(-1)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
 
tmp = 1
for num in A:
    tmp *= num
    if tmp > 1e18:
      break
  
if tmp <= 1e18:
    print(tmp)
elif 0 in A:
    print(0)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = map(int, input().split())

tmp = 1
for num in A:
    tmp *= num
if tmp <= 1e18:
    print(tmp)
else:
    print(-1)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
 
tmp = 1
for num in A:
    tmp *= num
    if tmp > 1e18:
      break
  
if tmp <= 1e18:
    print(tmp)
elif 0 in A:
    print(0)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

tmp = 1
for num in A:
    tmp *= num
if tmp <= 1e18:
    print(tmp)
else:
    print(-1)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
 
tmp = 1
for num in A:
    tmp *= num
    if tmp > 1e18:
      break
  
if tmp <= 1e18:
    print(tmp)
elif 0 in A:
    print(0)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
string = int(input())

if string=="ABC":
    print("ARC")
elif string=="ARC":
    print("ABC")


Fixed submission:
string = input()

if string=="ABC":
    print("ARC")
elif string=="ARC":
    print("ABC")
Buggy python submission (verdict: Runtime Error):
import numpy as np

N,M = map(int, input().split())
score = list(map(int, input().split()))
adj_mat = np.zeros((N,N))

for _ in range(M):
    A,B = map(int, input().split())
    adj_mat[A-1, B-1] = 1
    adj_mat[B-1, A-1] = 1

score_ = 0
for i, adjs in enumerate(adj_mat):
    is_max = True
    for adj in np.where(adjs==1)[0]:
        if score[i] <= score[adj]:
            is_max = False
    if is_max:
        score_+=1
print(score_)


Fixed submission:
import numpy as np

N,M = map(int, input().split())
score = list(map(int, input().split()))
adj_list = [[] for _ in range(N)]

for _ in range(M):
    A,B = map(int, input().split())
    adj_list[A-1].append(B-1)
    adj_list[B-1].append(A-1)

score_ = 0
for i, adjs in enumerate(adj_list):
    is_max = True
    for adj in adjs:
        if score[i] <= score[adj]:
            is_max = False
    if is_max:
        score_+=1
print(score_)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    n, x, m = map(int, args[0].split())

    a = x
    ret = 0
    D = [0]*(m+1)
    for i in range(n):
        if 0 < D[a]:
            j = a
            L = []
            while D[j] != a:
                L.append(j)
                j = D[j]
            L.append(j)
            d, r = divmod(n-i-1, len(L))
            ret += d*sum(L)+sum(L[:r+1])
            break
        ret += a
        p = a
        a = pow(a, 2, m)
        D[p] = a

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    n, x, m = map(int, args[0].split())

    a = x
    ret = 0
    D = [-1]*(m+1)
    for i in range(n):
        if 0 <= D[a]:
            j = a
            L = []
            while D[j] != a:
                L.append(j)
                j = D[j]
            L.append(j)
            d, r = divmod(n-i-1, len(L))
            ret += d*sum(L)+sum(L[:r+1])
            break
        ret += a
        p = a
        a = pow(a, 2, m)
        D[p] = a

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = tuple(map(int, args[1].split()))

    l, r = 1, max(A)
    while 1e-3 < r-l:
        m = (l+r)/2
        cnt = 0
        for a in A:
            cnt += -int(-a//m)-1

        if k < cnt:
            l = m
        else:
            r = m

    return str(-int(-l//1))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8

def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = tuple(map(int, args[1].split()))

    l, r = 1, max(A)
    while 0.1 < r-l:
        m = (l+r)/2
        cnt = 0
        for a in A:
            cnt += -int(-a//m)-1

        if k < cnt:
            l = m
        else:
            r = m

    return str(-int(-l//1))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = map(int, args[1].split())

    ret = 1
    for a in A:
        if 10**18 < ret*a:
            ret = -1
        else:
            ret *= a

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))
    A.sort()

    ret = 1
    for a in A:
        if 10**18 < ret*a:
            ret = -1
            break
        else:
            ret *= a

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = np.array(list(map(int, args[1].split())))

    ret = 0
    for i in range(1, n):
        ret += n-i-np.count_nonzero(A[i:]+A[:-i]-i)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8
from bisect import bisect_left
from collections import defaultdict


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    ret = 0
    X = defaultdict(list)
    for i, a in enumerate(A):
        X[a+i].append(i)

    for j, a in enumerate(A):
        if 0 <= j-a:
            ret += bisect_left(X[j-a], j)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Runtime Error):
# coding: utf-8


def solve(*args: str) -> str:
    n, m, q = map(int, args[0].split())
    ABCD = [tuple(map(int, abcd.split())) for abcd in args[1:]]

    ret = 0
    stack = [(0, '')]
    while stack:
        d, s = stack.pop()
        S = s+str(d)
        if len(S) == m:
            ret = max(
                ret,
                sum([d for a, b, c, d in ABCD if int(S[b-1])-int(S[a-1]) == c])
            )
            continue

        for i in range(d, 10):
            stack.append((i, S))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    n, m, q = map(int, args[0].split())
    ABCD = [tuple(map(int, abcd.split())) for abcd in args[1:]]

    ret = 0
    stack = [(i, '') for i in range(10)]
    while stack:
        t, s = stack.pop()
        S = s+str(t)
        if len(S) == n:
            ret = max(
                ret,
                sum([d for a, b, c, d in ABCD if int(S[b-1])-int(S[a-1]) == c])
            )
            continue

        for i in range(t, m):
            stack.append((i, S))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
import math


def solve(*args: str) -> str:
    r = int(args[0])

    return str(2*math.pi()*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8
import math


def solve(*args: str) -> str:
    r = int(args[0])

    return str(2*math.pi*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
import math


def solve(*args: str) -> str:
    r = int(args[0])

    return str(2*math.pi()*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8
import math


def solve(*args: str) -> str:
    r = int(args[0])

    return str(2*math.pi*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from itertools import permutations


def solve(*args: str) -> str:
    k, n = map(int, args[0].split())
    A = list(map(int, args[1].split()))

    ret = k+1
    for P in permutations(A):
        total = 0
        cur = P[0]
        for a in P[1:]:
            total += min(abs(k-a)+cur, abs(a-cur))
            cur = a
        ret = min(ret, total)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    k, n = map(int, args[0].split())
    A = list(map(int, args[1].split()))

    D = [k-A[-1]+A[0]] + [A[i+1]-A[i] for i in range(n-1)]

    return str(k-max(D))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = np.array([int(a) for a in args[1]])

    for i in range(n-1):
        A = np.abs(A[:-1]-A[1:])

    return str(A[0])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = [ord(a)-48 for a in args[1]]

    A = [abs(A[i]-A[i+1]) for i in range(n-1)]
    r = 2 if A.count(1) == 0 else 1

    ret = 0
    for i in range(n-1):
        ret += (A[i]//r)*(n-2 == (i | (n-2-i)))

    return str((ret % 2)*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    X = np.argsort(A)
    Y = np.argsort(B)

    cmax = 0
    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))
        cmax = max(cmax, int(c))
    ret = A[X[0]]+B[Y[0]]

    for x in X:
        for y in Y:
            if ret < A[x]+B[y]-cmax:
                break
            ret = min(ret, A[x]+B[y]-XYC.get((x, y), 0))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))

    ret = min(A)+min(B)
    for (x, y), c in XYC.items():
        ret = min(ret, A[x]+B[y]-c)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))

    ret = 10**12
    for x in range(a):
        for y in range(b):
            ret = min(ret, A[x]+B[y]-XYC.get((x, y), 0))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))

    ret = min(A)+min(B)
    for (x, y), c in XYC.items():
        ret = min(ret, A[x]+B[y]-c)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from itertools import combinations


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = list(map(int, args[1].split()))

    D = [a*b for a, b in combinations(A, 2)]
    D.sort()

    return str(D[k-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(map(int, args[1].split())))
    N = A[A < 0]
    P = A[0 < A]

    count = 0
    left, right = -10**18, 10**18
    while left+1 < right:
        x = (left+right)//2
        count = 0

        if k <= len(N)*len(P):
            count += (len(P)-np.searchsorted(P, -(-x//N), side='left')).sum()

        elif (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2 < k:
            for D in (-(N[::-1]), P):
                count += np.searchsorted(D, x//D, side='right').sum()
                count -= len(D[D*D <= x])
            count //= 2
            count += (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2

        else:
            right = 0
            break

        if count < k:
            left = x
        else:
            right = x

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from itertools import combinations


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = list(map(int, args[1].split()))

    D = [a*b for a, b in combinations(A, 2)]
    D.sort()

    return str(D[k-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(map(int, args[1].split())))
    N = A[A < 0]
    P = A[0 < A]

    count = 0
    left, right = -10**18, 10**18
    while left+1 < right:
        x = (left+right)//2
        count = 0

        if k <= len(N)*len(P):
            count += (len(P)-np.searchsorted(P, -(-x//N), side='left')).sum()

        elif (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2 < k:
            for D in (-(N[::-1]), P):
                count += np.searchsorted(D, x//D, side='right').sum()
                count -= len(D[D*D <= x])
            count //= 2
            count += (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2

        else:
            right = 0
            break

        if count < k:
            left = x
        else:
            right = x

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    P = list(map(int, args[1].split()))

    ret = 0
    for i in range(n-k+1):
        ret = max(ret, (sum(P[i:i+k])+k)/2)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    P = list(map(int, args[1].split()))

    S = [0]*(n+1)
    for i, p in enumerate(P):
        S[i+1] += S[i] + P[i]

    ret = 0
    for i in range(k, n+1):
        ret = max(ret, (S[i]-S[i-k]+k)/2)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    h, n = map(int, args[0].split())

    AB = [tuple(map(int, s.split())) for s in args[1:]]

    inf = 10**12
    dp = [inf]*(h+1)
    dp[0] = 0
    for a, b in AB:
        for i, m in enumerate(dp):
            k = min(h, i+a)
            dp[k] = min(dp[k], dp[i]+b)

    return str(dp[-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    h, n = map(int, args[0].split())

    AB = [tuple(map(int, s.split())) for s in args[1:]]

    inf = 10**12
    dp = [inf]*(h+1)
    dp[0] = 0
    for a, b in AB:
        for i, m in enumerate(dp):
            k = min(h, i+a)
            dp[k] = min(dp[k], dp[i]+b)

    return str(dp[-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    P = list(map(int, args[1].split()))

    count = 0
    for i in range(n):
        b = True
        for j in range(i+1):
            b &= P[i] <= P[j]
        if b:
            count += 1

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    P = list(map(int, args[1].split()))

    count = 0
    small = P[0]
    for i in range(n):
        if P[i] <= small:
            count += 1
        small = min(small, P[i])

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    a = 1

    for m in range(n, 1, -2):
        a *= m

    ret = 0
    for s in reversed(str(a)):
        if s == '0':
            ret += 1
        else:
            break

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])

    if n % 2 != 0:
        return '0'

    ret = 0
    d = 10
    while d <= n:
        ret += n//d
        d *= 5

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = 0
    for i in range(1000):
        iii = '{:03d}'.format(i)
        j = 0
        for k in range(n):
            if s[k] == iii[j]:
                j += 1
                if j == 3:
                    ret += 1
                    break

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = 0

    index = [[] for _ in range(10)]
    for i in range(n):
        index[int(s[i])].append(i)

    for i in range(1000):
        iii = '{:03d}'.format(i)
        cur = -1
        found = False

        for e, j in enumerate(iii):
            found = False

            for k in index[int(j)]:
                if cur < k:
                    found = True
                    cur = k
                    break

            if not found:
                break

        if found:
            ret += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import itertools


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = len(set(''.join(c) for c in itertools.combinations(s, 3)))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = 0

    index = [[] for _ in range(10)]
    for i in range(n):
        index[int(s[i])].append(i)

    for i in range(1000):
        iii = '{:03d}'.format(i)
        cur = -1
        found = False

        for e, j in enumerate(iii):
            found = False

            for k in index[int(j)]:
                if cur < k:
                    found = True
                    cur = k
                    break

            if not found:
                break

        if found:
            ret += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
import math


def solve(*args: str) -> str:
    _ = int(args[0])
    D = sorted(list(map(int, args[1].split())))

    max_d = D[-1]

    nodes = [0]*(max_d+1)
    for d in D:
        nodes[d] += 1

    ret = 1
    for i in range(max_d+1):
        if i < 2:
            ret *= 1 if 0 < nodes[i] else 0
        else:
            h = math.factorial(nodes[i-1] + nodes[i]-1)
            h //= math.factorial(nodes[i])
            ret *= h

    return str(ret % 998244353)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    _ = int(args[0])
    D = list(map(int, args[1].split()))

    max_d = max(D)

    nodes = [0]*(max_d+1)
    for d in D:
        nodes[d] += 1

    ret = 0
    if D[0] == 0 and nodes.count(0) == 0 and nodes[0] == 1:
        ret = 1
        for i in range(2, max_d+1):
            ret *= pow(nodes[i-1], nodes[i], 998244353)

    return str(ret % 998244353)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = sorted(list(map(int, args[1].split())))
    F = sorted(list(map(int, args[2].split())), reverse=True)

    for _ in range(k):
        if A[-1] == 0:
            break

        max_af = 0
        max_i = -1

        for i in range(n):
            af = A[i]*F[i]
            if max_af < af:
                max_i = i
                max_af = af

        A[max_i] -= 1
        A.sort()

    ret = 0
    for i in range(n):
        ret = max(ret, A[i]*F[i])

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().split('\n'))))


Fixed submission:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(list(map(int, args[1].split()))))
    F = np.array(sorted(list(map(int, args[2].split())), reverse=True))

    right = 1+A[-1]*F[0]
    left = -1

    total = A.sum()
    while left+1 < right:
        mid = (left+right)//2
        if total - np.minimum(A, mid//F).sum() <= k:
            right = mid
        else:
            left = mid

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().split('\n'))))