Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
x = list(map(int, input().split()))

import bisect

idx_r = bisect.bisect_left(x, 0)

if x[idx_r] == 0:
    idx_l = idx_r
else:
    idx_l = idx_r - 1

ans = 1000000007
    
# right
if 0 <= idx_r + K - 1 < N:
    ans_tmp = x[idx_r + K - 1]
    ans = min(ans, ans_tmp)

# left
if 0 <= idx_l - K + 1 < N:
    ans_tmp = -x[idx_l - K + 1]
    ans = min(ans, ans_tmp)

# right -> left
for i in range(N):
    if 0 <= idx_r - K + 1 + i < idx_r + i < N:
        ans_tmp = 2 * x[idx_r + i] - x[idx_r - K + 1 + i]
        ans = min(ans, ans_tmp)

# left -> right
for i in range(N):
    if 0 <= idx_l - i < idx_l + K - 1 - i < N:
        ans_tmp = x[idx_l + K - 1 - i] - 2 * x[idx_l - i]
        ans = min(ans, ans_tmp)

print(ans)

Fixed submission:
# encoding: utf-8
import math
N, K = map(int, input().split())
x = list(map(int, input().split()))

# find position of Mr.Sunuke
for i_snk, xi in enumerate(x):
    if xi >= 0: break

# (left, right) * K patterns, left + right = K
min_dist = (x[-1] - x[0]) * K
for left in range(K + 1):
    right = K - left
    # skip
    # print("#", i_snk, left, right)
    if i_snk - left < 0: continue
    elif right + i_snk > N: continue
    # calc dist
    left_x = x[i_snk - left]
    right_x = x[i_snk + right - 1]
    tocorner = int(min(math.fabs(left_x), math.fabs(right_x)))
    side2side = right_x - left_x
    # print("##", i_snk, left_x, right_x, tocorner + side2side)
    if tocorner + side2side < min_dist: min_dist = tocorner + side2side

print(min_dist)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
x = list(map(int, input().split()))

import bisect

idx_r = bisect.bisect_left(x, 0)

if x[idx_r] == 0:
    idx_l = idx_r
else:
    idx_l = idx_r - 1

ans = 1000000007
    
# right
if 0 <= idx_r + K - 1 < N:
    ans_tmp = x[idx_r + K - 1]
    ans = min(ans, ans_tmp)

# left
if 0 <= idx_l - K + 1 < N:
    ans_tmp = -x[idx_l - K + 1]
    ans = min(ans, ans_tmp)

# right -> left
for i in range(N):
    if idx_r + i >= N or idx_r - K + 1 + i < 0: continue
    ans_tmp = 2 * x[idx_r + i] - x[idx_r - K + 1 + i]
    ans = min(ans, ans_tmp)

# left -> right
for i in range(N):
    if idx_l + K - 1 - i >= N or idx_l - i < 0: continue
    ans_tmp = x[idx_l + K - 1 - i] - 2 * x[idx_l - i]
    ans = min(ans, ans_tmp)

print(ans)

Fixed submission:
# encoding: utf-8
import math
N, K = map(int, input().split())
x = list(map(int, input().split()))

# find position of Mr.Sunuke
for i_snk, xi in enumerate(x):
    if xi >= 0: break

# (left, right) * K patterns, left + right = K
min_dist = (x[-1] - x[0]) * K
for left in range(K + 1):
    right = K - left
    # skip
    # print("#", i_snk, left, right)
    if i_snk - left < 0: continue
    elif right + i_snk > N: continue
    # calc dist
    left_x = x[i_snk - left]
    right_x = x[i_snk + right - 1]
    tocorner = int(min(math.fabs(left_x), math.fabs(right_x)))
    side2side = right_x - left_x
    # print("##", i_snk, left_x, right_x, tocorner + side2side)
    if tocorner + side2side < min_dist: min_dist = tocorner + side2side

print(min_dist)
Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
N, M = list(map(int, input().split()))

# TLE
# Amod = [A for A in map(lambda x: int(x) % M , input().split())]
# ans = 0
# for l in range(len(Amod)):
#     acm = 0
#     for r in range(l, len(Amod)):
#         acm = (acm + Amod[r]) % M
#         if acm == 0: ans += 1

Asym = []

sym = 0
cnt_zero = 0
for i, A in enumerate(map(int, input().split())):
    sym = (sym + A) % M
    if sym > 0: Asym.append(sym)
    else: cnt_zero += 1
        
ans = cnt_zero * (cnt_zero + 1)
# for sym in set(Asym):
#     cnt = Asym.count(sym)
#     ans += cnt * (cnt -  1)
        
print(int(ans / 2))

# speed test

# Acnt = [0 for i in range(M)]
# sym = 0
# for A in map(int, input().split()):
#     sym = (sym + A) % M
#     Acnt[sym] += 1

# print(int(Acnt[0] + sum([cnt * (cnt - 1) for cnt in Acnt]) / 2))


Fixed submission:
# encoding: utf-8

n, k = input().split()

if int(n) % int(k) == 0: print(0)
else: print(1)

Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
N, M = list(map(int, input().split()))

# TLE
Amod = [A for A in map(lambda x: int(x) % M ,filter(lambda x: int(x) % M > 0, input().split()))]
ans = 0
for l in range(len(Amod)):
    acm = 0
    for r in range(l, len(Amod)):
        acm = (acm + Amod[r]) % M
        if acm == 0: ans += 1

print(ans)

Fixed submission:
# encoding: utf-8

n, k = input().split()

if int(n) % int(k) == 0: print(0)
else: print(1)

Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
N, M = list(map(int, input().split()))

# TLE
Amod = [A for A in map(lambda x: int(x) % M ,filter(lambda x: int(x) % M > 0, input().split()))]
ans = 0
for l in range(len(Amod)):
    acm = 0
    for r in range(l, len(Amod)):
        acm = (acm + Amod[r]) % M
        if acm == 0: ans += 1


Fixed submission:
# encoding: utf-8

n, k = input().split()

if int(n) % int(k) == 0: print(0)
else: print(1)
Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

ans = max(A) - min(A)
for b2 in range(2, N - 1):
    # b1
    # tar = -sum(A[b2:])
    tar = -(Asum[N] - Asum[b2])
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    # tar = Asum[:b2]
    tar = Asum[b2]
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    # print("#", A[:b1], A[b1:b2], A[b2:b3], A[b3:], parts)
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

Fixed submission:
# encoding: utf-8
N = int(input())
if N % 2: print(2 * N)
else: print(N)
Buggy python submission (verdict: Runtime Error):
2 6 3


Fixed submission:
# encoding: utf-8
ABC = sorted(list(map(int, input().split())))

diff0 = ABC[-1] - ABC[0]
diff1 = ABC[-1] - ABC[1]

# +2 only
if diff0 % 2 == diff1 % 2 == 0: ans = (diff0 + diff1) // 2
# +1 (ABC[0], ABC[1]) once and +2
elif diff0 % 2 == diff1 % 2 == 1: ans = (diff0 + diff1) // 2
# +1 (ABC[{0, 1}], ABC[2]) once and +2)
else: ans = 1 + (diff0 + diff1 + 2) // 2

print(ans)
Buggy python submission (verdict: Runtime Error):
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

MAGIC_NUMBER = 100000
isprime = [True] * (MAGIC_NUMBER + 1)
for p in range(2, MAGIC_NUMBER + 1):
    if not isprime[p]: continue
    i_p = 2
    while p * i_p <= MAGIC_NUMBER:
        isprime[p * i_p] = False
        i_p += 1

primes = []
for p in range(2, MAGIC_NUMBER + 1):
    if isprime[p]: primes.append(p)

candidates = []
for p in primes:
    if p % 2 == 0: continue
    #
    if isprime[(p + 1) // 2]: candidates.append(p)


import bisect
    
for i, (li, ri) in enumerate(lr):
    i_l = bisect.bisect_left(candidates, li)
    i_r = bisect.bisect_left(candidates, ri)
    #
    if candidates[i_r] == ri: i_r += 1
    print(i_r - i_l)

Fixed submission:
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

MAGIC_NUMBER = 100000
isprime = [True] * (MAGIC_NUMBER + 1)
for p in range(2, MAGIC_NUMBER + 1):
    if not isprime[p]: continue
    i_p = 2
    while p * i_p <= MAGIC_NUMBER:
        isprime[p * i_p] = False
        i_p += 1

primes = []
for p in range(2, MAGIC_NUMBER + 1):
    if isprime[p]: primes.append(p)

candidates = []
for p in primes:
    if p % 2 == 0: continue
    #
    if isprime[(p + 1) // 2]: candidates.append(p)


import bisect
    
for i, (li, ri) in enumerate(lr):
    i_l = bisect.bisect_left(candidates, li)
    i_r = bisect.bisect_left(candidates, ri)
    #
    if i_r < len(candidates) and candidates[i_r] == ri: i_r += 1
    print(i_r - i_l)
Buggy python submission (verdict: Time Limit Exceeded):
# encoding: utf-8
import sys

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

# num of Ai each Bi can lift
capacity_B = [0] * N
idx_A = 0
idx_B = 0
for i in range(2 * N):
    if idx_B == N: break
    elif idx_A == N:
        for i in range(idx_B, N): capacity_B[i] = N
    elif A[idx_A] >= B[idx_B]:
        capacity_B[idx_B] = idx_A
        idx_B += 1
    else:
        idx_A += 1
        
# print("#", capacity_B)

# num of Bi each Ci can lift
capacity_C = [0] * N
idx_B = 0
idx_C = 0
for i in range(2 * N):
    if idx_C == N: break
    elif idx_B == N:
        for i in range(idx_C, N): capacity_C[i] = N
    elif B[idx_B] >= C[idx_C]:
        capacity_C[idx_C] = idx_B
        idx_C += 1
    else:
        idx_B += 1

# print("#", capacity_C)

# num of (Ai, Bi) each Ci can lift
stacked = [0] * N
idx_AB = 0
idx_BC = 0
sum_tmp = 0
for i in range(2 * N):
    if idx_BC == N: break
    elif idx_AB == N:
        for i in range(idx_BC, N): stacked[i] = sum_tmp
    elif idx_AB >= capacity_C[idx_BC]:
        stacked[idx_BC] = sum_tmp
        idx_BC += 1
    else:
        sum_tmp += capacity_B[idx_AB]
        idx_AB += 1

# print("#", stacked)

# the answer is sum of All
print(sum(stacked))

Fixed submission:
# encoding: utf-8
import sys

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

### TLE test in NlogN ###

# num of Ai each Bi can lift
capacity_B = [0] * N
idx_A = 0
idx_B = 0
for i in range(2 * N):
    if idx_B == N: break
    elif idx_A == N:
        for i in range(idx_B, N): capacity_B[i] = N
        break # oh...
    elif A[idx_A] >= B[idx_B]:
        capacity_B[idx_B] = idx_A
        idx_B += 1
    else:
        idx_A += 1
        
# print("#", capacity_B)

# num of Bi each Ci can lift
capacity_C = [0] * N
idx_B = 0
idx_C = 0
for i in range(2 * N):
    if idx_C == N: break
    elif idx_B == N:
        for i in range(idx_C, N): capacity_C[i] = N
        break # oh...
    elif B[idx_B] >= C[idx_C]:
        capacity_C[idx_C] = idx_B
        idx_C += 1
    else:
        idx_B += 1

# print("#", capacity_C)

# sum of [num of (Ai, Bi) each Ci can lift]
ans = 0
idx_AB = 0
idx_BC = 0
sum_tmp = 0
for i in range(2 * N):
    if idx_BC == N: break
    elif idx_AB == N:
        for i in range(idx_BC, N): ans += sum_tmp
        break # oh...
    elif idx_AB >= capacity_C[idx_BC]:
        ans += sum_tmp
        idx_BC += 1
    else:
        sum_tmp += capacity_B[idx_AB]
        idx_AB += 1

# print("#", stacked)

print(ans)
Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
N = int(input())
A = list(map(int, input().split()))

A.sort()

view = 10 * 9 + 7
lengths = [0] * 2
idx = 0
for Ai in reversed(A):
    if Ai < view:
        view = Ai
        cnt = 0
    cnt += 1
    if cnt >= 2:
        lengths[idx] = view
        cnt = 0
        idx += 1
    if idx > 1: break

# print("#", lengths)
print(lengths[0] * lengths[1] if idx > 1 else 0)

Fixed submission:
# encoding: utf-8
N = int(input())
A = list(map(int, input().split()))

A.sort()

view = 10 ** 9 + 7
lengths = [0] * 2
idx = 0
for Ai in reversed(A):
    if Ai < view:
        view = Ai
        cnt = 0
    cnt += 1
    if cnt >= 2:
        lengths[idx] = view
        cnt = 0
        idx += 1
    if idx > 1: break

# print("#", lengths)
print(lengths[0] * lengths[1] if idx > 1 else 0)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

i = j = 0

passed = [[None] * W for _ in range(H)]

def dp(i, j):
    global H, W
    passed[i][j] = True
    if i == H - 1 and j == W - 1: return True
    #
    if i + 1 >= H:
        d = False
    else:
        d = (A[i + 1][j] == '#')
    #
    if j + 1 >= W:
        r = False
    else:
        r = (A[i][j + 1] == '#')
    #
    if d and not r:
        return dp(i + 1, j)
    elif not d and r:
        return dp(i, j + 1)
    else:
        return False

if dp(0, 0):
    ans = 'Possible'
    for i in range(H):
        for j in range(W):
            if not visited[i][j] and A[i][j] == '#':
                ans = 'Impossible'
    #
    print(ans)
else:
    print('Impossible')

Fixed submission:
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

i = j = 0

visited = [[None] * W for _ in range(H)]

def dp(i, j):
    global H, W
    visited[i][j] = True
    if i == H - 1 and j == W - 1: return True
    #
    if i + 1 >= H:
        d = False
    else:
        d = (A[i + 1][j] == '#')
    #
    if j + 1 >= W:
        r = False
    else:
        r = (A[i][j + 1] == '#')
    #
    if d and not r:
        return dp(i + 1, j)
    elif not d and r:
        return dp(i, j + 1)
    else:
        return False

if dp(0, 0):
    ans = 'Possible'
    for i in range(H):
        for j in range(W):
            if not visited[i][j] and A[i][j] == '#':
                ans = 'Impossible'
    #
    print(ans)
else:
    print('Impossible')
Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
N, K = map(int, input().split())
D = list(map(int, input().split()))

Db = []
for Di in range(10):
    if Di not in D: Db.append(Di)
# print("#", Db)

for level in range(6):
    if N // (10 ** level) < 1: break
# print("#", level)
    
memo = [None] * (level * 10000)
    
def pay(pos, tmp):
    # print("##", pos, tmp)
    if pos > level or tmp >= N:
        if tmp >= N:
            # print("###", tmp)
            return tmp
        else: return 10000
    elif memo[pos * 10000 + tmp] != None: return memo[pos * 10000 + tmp]
    rets = []
    for Dbi in Db:
        add = Dbi * (10 ** pos)
        rets.append(pay(pos + 1, tmp + add))
    ret = min(rets)
    if memo[pos * 10000 + tmp] == None: memo[pos * 10000 + tmp] = ret    
    return ret

print(pay(0, 0))

Fixed submission:
# encoding: utf-8
N, K = map(int, input().split())
D = list(map(int, input().split()))

Db = []
for Di in range(10):
    if Di not in D: Db.append(Di)
# print("#", Db)

for level in range(6):
    if N // (10 ** level) < 1: break
# print("#", level)
    
memo = [None] * ((level + 1) * 10000)
    
def pay(pos, tmp):
    # print("##", pos, tmp)
    if pos > level or tmp >= N:
        if tmp >= N:
            # print("###", tmp)
            return tmp
        else: return 10000
    elif memo[pos * 10000 + tmp] != None: return memo[pos * 10000 + tmp]
    rets = []
    for Dbi in Db:
        add = Dbi * (10 ** pos)
        rets.append(pay(pos + 1, tmp + add))
    ret = min(rets)
    if memo[pos * 10000 + tmp] == None: memo[pos * 10000 + tmp] = ret    
    return ret

print(pay(0, 0))
Buggy python submission (verdict: Runtime Error):
def resolve():
	X = int(input())
	if 400<= x < 600:
		print(8); return
	elif 600<= x < 800:
		print(7); return
	elif 800<= x < 1000:
		print(6); return
	elif 1000<= x < 1200:
		print(5); return
	elif 1200<= x < 1400:
		print(4); return
	elif 1400<= x < 1600:
		print(3); return
	elif 1600<= x < 1800:
		print(2); return
	elif 1800<= x < 2000:
		print(1); return
resolve()

Fixed submission:
def resolve():
	x = int(input())
	if 400<= x < 600:
		print(8); return
	elif 600<= x < 800:
		print(7); return
	elif 800<= x < 1000:
		print(6); return
	elif 1000<= x < 1200:
		print(5); return
	elif 1200<= x < 1400:
		print(4); return
	elif 1400<= x < 1600:
		print(3); return
	elif 1600<= x < 1800:
		print(2); return
	elif 1800<= x < 2000:
		print(1); return
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
def resolve():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(list(map(int, input().split())))
    dic = Counter(A)
    for i in BC:
        B, C = i[0], i[1]
        dic[C] += dic[B]
        dic[B] = 0
        ans = 0
        for k, v in dic.items():
            ans += int(k)*v
        print(ans)

resolve()

Fixed submission:
def resolve():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(list(map(int, input().split())))
    dic = Counter(A)
    ans = 0
    for k, v in dic.items():
        ans += int(k)*v
    for i in BC:
        B, C = i[0], i[1]
        ans += - B*dic[B] + C*dic[B]
        dic[C] += dic[B]
        del dic[B]
        print(ans)

resolve()

Buggy python submission (verdict: Time Limit Exceeded):
def resolve():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(list(map(int, input().split())))
    dic = Counter(A)
    for i in BC:
        B, C = i[0], i[1]
        dic[C] += dic[B]
        dic[B] = 0
        ans = 0
        for k, v in dic.items():
            ans += int(k)*v
        print(ans)

resolve()

Fixed submission:
def resolve():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(list(map(int, input().split())))
    dic = Counter(A)
    ans = 0
    for k, v in dic.items():
        ans += int(k)*v
    for i in BC:
        B, C = i[0], i[1]
        ans += - B*dic[B] + C*dic[B]
        dic[C] += dic[B]
        del dic[B]
        print(ans)

resolve()
Buggy python submission (verdict: Runtime Error):
def resolve():
    x, n = map(int, input().split())
    if n == 0:
        print(x)
        return
    else:
        p = [int(i) for i in input().split()]

    s = []
    for i in range(101):
        if not i in p:
            s.append(i)
    if not x in p:
        print(x)
        return
    
    t = s + [x]
    t.sort()
    pos = t.index(x)
    if abs(x-t[pos-1]) <= abs(x-t[pos+1]):
        print(t[pos-1])
        return
    else:
        print(t[pos+1])

resolve()


Fixed submission:
def resolve():
    x, n = map(int, input().split())
    if n == 0:
        print(x)
        return
    else:
        p = [int(i) for i in input().split()]

    i = 0
    while True:
        if not x-i in p:
            print(x-i)
            return
        if not x+i in p:
            print(x+i)
            return
        i += 1

resolve()

Buggy python submission (verdict: Runtime Error):
def resolve():
    x, n = map(int, input().split())
    if n == 0:
        print(x)
        return
    else:
        p = [int(i) for i in input().split()]

    s = []
    for i in range(101):
        if not i in p:
            s.append(i)
    if not x in p:
        print(x)
        return
    
    t = s + [x]
    t.sort()
    pos = t.index(x)
    if abs(x-t[pos-1]) <= abs(x-t[pos+1]):
        print(t[pos-1])
    else:
        print(t[pos+1])

resolve()

Fixed submission:
def resolve():
    x, n = map(int, input().split())
    if n == 0:
        print(x)
        return
    else:
        p = [int(i) for i in input().split()]

    i = 0
    while True:
        if not x-i in p:
            print(x-i)
            return
        if not x+i in p:
            print(x+i)
            return
        i += 1

resolve()
Buggy python submission (verdict: Runtime Error):
import math
A, B, H, M = map(int, input().split())
l = (360/60)*M
s = (360/12)*H + (360/12/60)*M
theta = max(l, s) - min(l, s)
theta = min(theta, 360-theta)
print(math.sqrt(A**2 + B**2 - 2*A*B*math.cos(math.radians(theta))))

Fixed submission:
n = str(input())
if int(n[-1]) in [2, 4, 5, 7, 9]:
    print("hon")
elif int(n[-1]) in [0, 1, 6, 8]:
    print("pon")
else:
    print("bon")
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
lmax = 0
rmin = 10**5
for i in range(M):
    L, R = map(int, input().split())
    lmax = max(lmax, L)
    rmin = min(rmin, R)
ans = rmin - lmax
if ans >= 0:
    print(ans + 1)
else:
    print(0)

Fixed submission:
R, D, X = map(int, input().split())
for i in range(10):
    X = X*R - D
    print(X)
Buggy python submission (verdict: Runtime Error):
from math import ceil

def isOK(length):
  ans = 0
  for a in A:
    ans += ceil(a / length) - 1
  return ans <= k


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

start, end = 0, 10**9 + 1
while True:
  mid = (start + end) // 2
  prev = mid - 1
  if isOK(mid):
    if isOK(prev):
      end = mid
    else:
      print(mid)
      exit()
  else:
    start = mid


Fixed submission:
from math import ceil

def isOK(length):
  ans = 0
  for a in A:
    ans += ceil(a / length) - 1
  return ans <= k

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

start, end = 0, 10**9 + 1
while True:
  mid = (start + end) // 2
  if mid == 1:
    print(mid)
    exit()
  prev = mid - 1
  if isOK(mid):
    if isOK(prev):
      end = mid
    else:
      print(mid)
      exit()
  else:
    start = mid
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = sorted(list(map(int, input().split())), reverse = True)

points = []
for i in range(N):
  points = points + [As[i]] * (i+1)
print(sum(points[:N-1]))

Fixed submission:
N = int(input())
As = sorted(list(map(int, input().split())), reverse = True)
ans = As[0]
N -= 2

p = N // 2
ans += sum(As[1:1+p]) * 2

if N % 2 == 1:
  ans += As[1+p]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = sorted(list(map(int, input().split())))
A = As.pop()
N -= 1
between = [A]

ans = 0
while N > 0:
  point = between.pop()
  ans += point

  A = As.pop()
  N -= 1
  between = [A, A] + between
print(ans)

Fixed submission:
N = int(input())
As = sorted(list(map(int, input().split())), reverse = True)
ans = As[0]
N -= 2

p = N // 2
ans += sum(As[1:1+p]) * 2

if N % 2 == 1:
  ans += As[1+p]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())

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

acA = [0]
for i in range(n):
  acA.append(acA[i] + A[i])

acB = [0]
for i in range(m):
  acB.append(acB[i] + B[i])

ans = 0
for a in range(n+1):
  for b in range(m+1):
    if acA[a] + acB[b] <= k:
      ans = max(ans, a + b)
    else:
      break

print(ans)

Fixed submission:
import bisect

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

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

acA = [0]
for i in range(n):
  acA.append(acA[i] + A[i])

acB = [0]
for i in range(m):
  acB.append(acB[i] + B[i])

ans = 0
for a in range(n+1):
  if k-acA[a] < 0: break
  b = bisect.bisect(acB, k-acA[a]) - 1
  ans = max(ans, a+b)
    
print(ans)