Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
class TrieNode:
    def __init__(self, char):
        self.char = char
        self.nextnode = dict()
        self.is_indict = False


class Trie:
    def __init__(self, charset):
        self.charset = charset
        self.root = TrieNode('')

    def add(self, a_str):
        node = self.root
        for i, char in enumerate(a_str):
            if char not in node.nextnode:
                node.nextnode[char] = TrieNode(char)
            node = node.nextnode[char]
            if i == len(a_str) - 1:
                node.is_indict = True

    def dfs(self, node, dep):
        ret, cnt = 0, 0
        for s in '01':
            if s not in node.nextnode:
                cnt += 1
            else:
                ret ^= self.dfs(node.nextnode[s], dep + 1)
        dep += 1
        if cnt % 2:
            power2 = 0
            while dep > 0 and dep % 2 == 0:
                power2 += 1
                dep //= 2
            ret ^= 2 ** power2
        return ret

    def debug_output(self, node, now):
        print(node.char, list(node.nextnode.items()), node.is_indict, now)
        if node.is_indict:
            print(now)
        for n in node.nextnode.values():
            self.debug_output(n, now + n.char)

N, L = map(int, input().split())
T = Trie('01')
for _ in range(N):
    T.add(input())
# T.debug_output(T.root, '')
print("Alice" if T.dfs(T.root, 0) else "Bob")


Fixed submission:
import sys
sys.setrecursionlimit(2 * 10 ** 5)


class TrieNode:
    def __init__(self, char):
        self.char = char
        self.nextnode = dict()
        self.is_indict = False


class Trie:
    def __init__(self, charset):
        self.charset = charset
        self.root = TrieNode('')

    def add(self, a_str):
        node = self.root
        for i, char in enumerate(a_str):
            if char not in node.nextnode:
                node.nextnode[char] = TrieNode(char)
            node = node.nextnode[char]
            if i == len(a_str) - 1:
                node.is_indict = True

    def dfs(self, node, dep):
        ret, cnt = 0, 0
        if node.is_indict:
            return 0
        for s in '01':
            if s not in node.nextnode:
                cnt += 1
            else:
                ret ^= self.dfs(node.nextnode[s], dep + 1)
        height = L - dep
        if cnt % 2:
            power2 = 0
            while height > 0 and height % 2 == 0:
                power2 += 1
                height //= 2
            ret ^= 2 ** power2
        return ret

    def debug_output(self, node, now):
        print(node.char, list(node.nextnode.items()), node.is_indict, now)
        if node.is_indict:
            print(now)
        for n in node.nextnode.values():
            self.debug_output(n, now + n.char)

N, L = map(int, input().split())
T = Trie('01')
for _ in range(N):
    T.add(input())
# T.debug_output(T.root, '')
print("Alice" if T.dfs(T.root, 0) else "Bob")
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)
non_x = []
s_notx = []
for i, s in enumerate(S):
    if s != 'x':
        non_x.append(i)
        s_notx.append(s)
s_notx = ''.join(s_notx)
if s_notx != s_notx[::-1]:
    print(-1)
    quit()

ans = 0
L = len(non_x)
if L % 2 == 0:
    left, right = L // 2 - 1, L // 2
else:
    left = right = L // 2
left, right = left - 1, right + 1
for i in range(left + 1):
    l, r = left - i, right + i
    ans += abs((non_x[l + 1] - non_x[l]) - (non_x[r] - non_x[r - 1]))
ans += abs(non_x[0] - (N - non_x[-1] - 1))
print(ans)


Fixed submission:
S = input()
N = len(S)
non_x = []
s_notx = []
for i, s in enumerate(S):
    if s != 'x':
        non_x.append(i)
        s_notx.append(s)
s_notx = ''.join(s_notx)
if s_notx != s_notx[::-1]:
    print(-1)
    quit()
if not non_x:
    print(0)
    quit()
ans = 0
L = len(non_x)
if L % 2 == 0:
    left, right = L // 2 - 1, L // 2
else:
    left = right = L // 2
left, right = left - 1, right + 1
for i in range(left + 1):
    l, r = left - i, right + i
    ans += abs((non_x[l + 1] - non_x[l]) - (non_x[r] - non_x[r - 1]))
ans += abs(non_x[0] - (N - non_x[-1] - 1))
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = [tuple(int(x) for x in input().split()) for _ in range(N)]
A = [(a, b) for a, b in A if a <= K]
# print(A)
L = K.bit_length()
ans = 0
for i in reversed(range(L)):
    bit = (1 << i) & K
    if bit != 1:
        # print(bit, ':', i)
        cand = 0
        bor = 0
        for a, b in A:
            if ((a >> i) & 1) == 0:
                # print(a, (a >> i) & 1)
                cand += b
                bor ^= a
        ans = max(ans, cand)
        assert(bor <= K)
print(ans)


Fixed submission:
N, K = map(int, input().split())
A = [tuple(int(x) for x in input().split()) for _ in range(N)]
A = [(a, b) for a, b in A if a <= K]
L = K.bit_length()
ans = sum(b for a, b in A if (a | K) <= K)
for i in reversed(range(L)):
    bit = (1 << i) & K
    if bit != 1:
        cand = 0
        bor = 0
        tmp_K = K & ~(1 << i) | ((1 << i) - 1)
        ans = max(ans, sum(b for a, b in A if (a | tmp_K) <= K))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N, M = map(int, input().split())
print("YES" if all(x % 2 == 0 for x in Counter(sum([list(map(int, input().split())) for _ in range(M)], [])).values()) else "NO")


Fixed submission:
from collections import Counter
N, M = map(int, input().split())
cnt = Counter()
for _ in range(M):
    a, b = map(int, input().split())
    cnt[a] += 1
    cnt[b] += 1
print("YES" if all(x % 2 == 0 for x in cnt.values()) else "NO")
Buggy python submission (verdict: Runtime Error):
import string
S = input()
N = len(S)
assert(len(S) <= 100)

for i in range(N):
    for j in range(i, N):
        s = S[i:j+1]
        if len(s) > 1 and any(s.count(a) * 2 > j-i+1 for a in string.ascii_lowercase):
            print(i+1, j+1)
            quit(0)
print(-1, -1)


Fixed submission:
import string
S = input()
N = len(S)

for i in range(N):
    if i < N-1 and S[i] == S[i+1]:
        print(i+1, i+2)
        quit()
    elif i < N-2 and S[i] == S[i+2]:
        print(i+1, i+3)
        quit()
print(-1, -1)
Buggy python submission (verdict: Runtime Error):
from math import gcd
N, X = map(int, input().split())
print(3 * (N - gcd(N, X)))


Fixed submission:
from fractions import gcd
N, X = map(int, input().split())
print(3 * (N - gcd(N, X)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(5000)


def dfs(v, parent, rest, edge):
    ret = 0
    for c in edge[v]:
        if c != parent:
            ret += dfs(c, v, rest - 1, edge)
    return ret + (rest <= 0)


def main(N, K, edge):
    ans = N
    if K % 2 == 0:
        for v in range(N):
            ans = min(ans, sum(dfs(c, v, K // 2, edge) for c in edge[v]))
    else:
        for v in range(N):
            for c in edge[v]:
                ans = min(ans, dfs(v, c, K // 2 + 1, edge) + dfs(c, v, K // 2 + 1, edge))
    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        edge[u].append(v)
        edge[v].append(u)
    main(N, K, edge)


Fixed submission:
import sys
sys.setrecursionlimit(5000)


def dfs(v, parent, rest, edge):
    ret = 0
    for c in edge[v]:
        if c != parent:
            ret += dfs(c, v, rest - 1, edge)
    return ret + (rest <= 0)


def main(N, K, edge):
    ans = N
    if K % 2 == 0:
        for v in range(N):
            ans = min(ans, sum(dfs(c, v, K // 2, edge) for c in edge[v]))
    else:
        for v in range(N):
            for c in edge[v]:
                ans = min(ans, dfs(v, c, K // 2 + 1, edge) + dfs(c, v, K // 2 + 1, edge))
    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        edge[u].append(v)
        edge[v].append(u)
    main(N, K, edge)
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll m = 1e9 + 7;
ll powm(ll b, ll p)
{
  if (p == 0)
  return 1;
  if (p % 2 == 1)
  return b * powm(b, p - 1) % m;
  else
  {
    ll t = powm(b, p / 2);
    return t * t % m;
  }
}
int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  map<int, int> flcm;
  vector<map<int, int>> b(n);
  for (int i = 0; i < n; i++)
  cin >> a[i];

  for (int i = 0; i < n; i++)
  {
    int t = a[i];
    for (ll j = 2; j * j <= t; j++)
    {
      while (t % j == 0)
      {
        b[i][j] += 1;
        t /= j;
      }
      if (b[i][j] > flcm[j])
      flcm[j] = b[i][j];
    }
    if (t != 1)
    {
      b[i][t]++;
      if (flcm[t] == 0)
      flcm[t] = 1;
    }
  }
  ll ans = 0;
  ll lcm = 1;
  for (auto x : flcm)
  {
    lcm = lcm * powm(x.first, x.second) % m;
  }
  for (int i = 0; i < n; i++) {
  	ans += lcm * powm(a[i], m - 2) % m;
  }
  cout << ans << endl;
}

Fixed submission:
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
def lcm(a, b):
    return a // gcd(a, b) * b

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

l = 1
for i in a:
    l = lcm(l, i)

ans = 0
for i in a:
    ans += l // i

print(ans % 1000000007)

Buggy python submission (verdict: Runtime Error):
from math import gcd

def lcm(a, b):
    return a // gcd(a, b) * b

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

l = 1
for i in a:
    l = lcm(l, i)

ans = 0
for i in a:
    ans += l // i

print(ans % 1000000007)

Fixed submission:
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
def lcm(a, b):
    return a // gcd(a, b) * b

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

l = 1
for i in a:
    l = lcm(l, i)

ans = 0
for i in a:
    ans += l // i

print(ans % 1000000007)
Buggy python submission (verdict: Runtime Error):
n = int(input())
mod = 10**9+ 7
a = list(map(int,input().split()))
ans = (sum(a)%mod)**2 - (sum[x**2 for x in a]%mod)
ans *= 5*10**8+4
ans %= mod
print(ans)

Fixed submission:
n = int(input())
mod = 10**9+ 7
a = list(map(int,input().split()))
ans = (sum(a)%mod)**2 - sum([x**2%mod for x in a])
ans *= 5*10**8+4
ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
a.sort()
data = [0 for _ in range(200001)]
for x in a:
    data[x] += 1

ans = 0
for i in range(1,200001):
    if not data[i]:continue
    if data[i] == 1:ans += 1
    j = i
    while j < 200001:
        data[j] = 0
        j += i

print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
a.sort()
data = [0 for _ in range(1000001)]
for x in a:
    data[x] += 1

ans = 0
for i in range(1,1000001):
    if not data[i]:continue
    if data[i] == 1:ans += 1
    j = i
    while j < 1000001:
        data[j] = 0
        j += i

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int, input().split())
a = list(map(int, input().split()))
event = []
data = [0 for _ in range(n+1)]
for i in range(k):
    data = [0 for _ in range(n + 1)]
    for i in range(n):
        data[max(0,i-a[i])] += 1
        data[min(n,i+a[i]+1)] -= 1

    for i in range(n):
        data[i+1] += data[i]

    a = data
print(*a[:n])

Fixed submission:
n,k = map(int, input().split())
a = list(map(int, input().split()))
event = []
for i in range(k):
    data = [0 for _ in range(n + 1)]
    for i in range(n):
        data[max(0,i-a[i])] += 1
        data[min(n,i+a[i]+1)] -= 1

    for i in range(n):
        data[i+1] += data[i]
    check = True
    for i in range(n):
        if data[i] != n:
            check = False
            break
    if check:
        print(*data[:n])
        exit()
    a = data
print(*a[:n])

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int, input().split())
a = list(map(int, input().split()))
check = []
for i in range(n):
    if a[i]:
        check.append([i,0,a[i]])
#print(check)
for i in range(k):
    if i!=0:
        a_next = a[:]
    else:
        a_next = [1 for _ in range(n)]
    change = set()
    for i,pre,now in check:
        for to in range(i+pre+1,i+now+1):
            if to >= n:break
            change.add(to)
            a_next[to] += 1
        for to in range(i-pre-1,i-now-1,-1):
            if to < 0:break
            change.add(to)
            a_next[to] += 1
        #print(a_next)
    check = []
    for to in change:
        check.append([to,a[to],a_next[to]])
    a = a_next

print(*a)

Fixed submission:
n,k = map(int, input().split())
a = list(map(int, input().split()))
event = []
for i in range(k):
    data = [0 for _ in range(n + 1)]
    for i in range(n):
        data[max(0,i-a[i])] += 1
        data[min(n,i+a[i]+1)] -= 1

    for i in range(n):
        data[i+1] += data[i]
    check = True
    for i in range(n):
        if data[i] != n:
            check = False
            break
    if check:
        print(*data[:n])
        exit()
    a = data
print(*a[:n])
Buggy python submission (verdict: Time Limit Exceeded):
n,s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for x in range(s+1):
        dp[i+1][x] = 2*dp[i][x]
        if x-a[i] >= 0:
            dp[i+1][x] += dp[i][x-a[i]]
        dp[i+1][x] %= mod

print(dp[n][s])

Fixed submission:
n,s = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 998244353
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for x in range(s+1):
        dp[i+1][x] = 2*dp[i][x]
        if x-a[i] >= 0:
            dp[i+1][x] += dp[i][x-a[i]]
        dp[i+1][x] %= mod

print(dp[n][s])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n,k = map(int, input().split())
a = list(map(lambda z:int(z)-1, input().split()))
if k <= n:
    now = 0
    for i in range(k):
        now = a[now]
    print(now+1)
    exit()
root = [0]
use = defaultdict(int)
now = 0
use[0] = 1
for i in range(n):
    now = a[now]
    if use[now] == 0:
        use[now] += i
        root.append(now)
    else:
        k -= use[now]
        root = root[use[now]:]
        break

k %= len(root)
print(root[k-1]+1)

Fixed submission:
from collections import defaultdict
n,k = map(int, input().split())
a = list(map(lambda z:int(z)-1, input().split()))
if k <= n:
    now = 0
    for i in range(k):
        now = a[now]
    print(now+1)
    exit()
root = [0]
use = [-1 for _ in range(n)]
use[0] = 0
now = 0
l = -1
for i in range(1,n+1):
    now = a[now]
    if use[now] == -1:
        use[now] = i
    else:
        k -= i
        l = i - use[now]
        break
k %= l
for i in range(k):
    now = a[now]
print(now+1)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()[::-1]
ans = 0
data = [0 for _ in range(2019)]
now = 0
data[0] = 1
for i,x in enumerate(s):
    now += int(x)*10**i
    now %= 2019
    data[now] += 1
    #print(now)

for i in range(2019):
    ans += data[i]*(data[i]-1)//2

print(ans)

Fixed submission:
s = input()[::-1]
n = len(s)
ans = 0
data = [0 for _ in range(2019)]
now = 0
data[0] = 1
q = [1]
x = 1
for i in range(n):
    x *= 10
    x %= 2019
    q.append(x)

for i,x in enumerate(s):
    now += int(x)*q[i]
    now %= 2019
    data[now] += 1
    #print(now)

for i in range(2019):
    ans += data[i]*(data[i]-1)//2

print(ans)
Buggy python submission (verdict: Runtime Error):
from heapq import *
x,y,a,b,c = map(int, input().split())
p = sorted(list(map(int, input().split())),reverse=True)[:x]
q = sorted(list(map(int, input().split())),reverse=True)[:y]
pq = sorted(p + q,reverse=True)

r = sorted(list(map(int, input().split())),reverse=True)
ans = 0
data_pq = [0]
for s in pq:
    data_pq.append(data_pq[-1] + s)

data_r = [0]
for t in r:
    data_r.append(data_r[-1] + t)


for i in range(c+1):
    ans = max(ans,data_r[i] + data_pq[x+y-i])

print(ans)

Fixed submission:
x,y,a,b,c = map(int, input().split())
p = sorted(list(map(int, input().split())),reverse=True)[:x]
q = sorted(list(map(int, input().split())),reverse=True)[:y]
pq = sorted(p + q,reverse=True)

r = sorted(list(map(int, input().split())),reverse=True)
ans = 0
data_pq = [0]
for s in pq:
    data_pq.append(data_pq[-1] + s)

data_r = [0]
for t in r:
    data_r.append(data_r[-1] + t)


for i in range(c+1):
    if x + y - i < 0:break
    ans = max(ans,data_r[i] + data_pq[x+y-i])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
r = 0
ans = s
for i in range(q):
    d = input().split()
    if len(d)==1:
        r += 1
    else:
        f = int(d[1])
        c = d[2]
        if (f+r)%2 == 1:
            ans = c + ans
        else:
            ans = ans + c

if r%2:
    ans = ans[::-1]
print(ans)

Fixed submission:
ans = input()
q = int(input())
r = 0
p = ""
for i in range(q):
    d = input().split()
    if len(d)==1:
        r += 1
    else:
        f = int(d[1])
        c = d[2]
        if (f+r)%2 == 1:
            p += c
        else:
            ans += c
ans = p[::-1] + ans
if r%2:
    ans = ans[::-1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n,p = map(int,input().split())
s = list(input())
s = [int(x) for x in s]
d1 = defaultdict(int)

ans = 0
for x in s:
    d2 = defaultdict(int)
    for y in d1.keys():
        z = (10*y + x)%p
        d2[z] += d1[y]
    d2[x%p] += 1
    ans += d2[0]
    d1 = d2

print(ans)

Fixed submission:
from collections import defaultdict
n,p = map(int,input().split())
s = list(input())
s = [int(x) for x in s][::-1]
if p != 2 and p != 5:
    ans = 0
    data = [0 for _ in range(p)]
    now = 1
    data[0] = 1
    a = 0
    for i in range(n):
        a += now*s[i]
        a %=p
        data[a]+=1
        now *= 10
        now %= p
    for x in data:
        ans += x*(x-1)//2
    print(ans)
if p == 2:
    ans = 0
    for i,x in enumerate(s[::-1]):
        if x%2 == 0:
            ans += i+1
    print(ans)
if p == 5:
    ans = 0
    for i,x in enumerate(s[::-1]):
        if x%5 == 0:
            ans += i+1
    print(ans)
Buggy python submission (verdict: Runtime Error):
n = input()
k = int(input())
m = len(n)
if k == 1:
    print(int(n[0])+9*(m-1))
elif k == 2:
    if m<2:ans = 0
    else:
        ans = 81*(m-1)*(m-2)//2
        ans += (int(n[0])-1)*(m-1)*9+int(n[1])+(m-2)*9
    print(ans)
else:
    if m<3:ans = 0
    else:
        ans1 = (m-1)*(m-2)*(m-3)//6*9**3
        ans2=(int(n[0])-1)*(m-1)*(m-2)//2*81
        ans3 =(m-2)*(m-3)//2*81
        ans = ans1+ans2+ans3
        if int(n[1]) > 0:
            ans += (int(n[1])-1)*(m-2)*9 + (m-3)*9+int(n[3])
    print(ans)

Fixed submission:
n = input()
k = int(input())
m = len(n)
if k == 1:
    print(int(n[0])+9*(m-1))
elif k == 2:
    if m<2:ans = 0
    else:
        ans = 81*(m-1)*(m-2)//2+(int(n[0])-1)*(m-1)*9
        for i in range(1,m):
            if int(n[i]) != 0:
                ans += (m-i-1)*9+int(n[i])
                break
    print(ans)
else:
    if m<3:ans = 0
    else:
        ans = (m-1)*(m-2)*(m-3)//6*9**3 + (int(n[0])-1)*(m-1)*(m-2)//2*81
        for i in range(1,m):
            if int(n[i])!=0:
                ans += (m-i-1)*(m-i-2)//2*81+(int(n[i])-1)*(m-i-1)*9
                break
        for j in range(i+1,m):
            if int(n[j]) != 0:
                ans += (m-j-1)*9+int(n[j])
                break
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
inf = 10**18
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
dp = [[inf]*(N+1) for _ in range(H+1)]
for h in range(H+1):
    for i in range(N+1):
        if i > 0 and h - AB[i - 1][0] > 0:
            dp[h][i] = min(dp[h][i-1], dp[h-AB[i-1][0]][i] + AB[i-1][1])
        elif i > 0:
            dp[h][i] = min(dp[h][i-1], AB[i-1][1])

print(dp[H][N])

Fixed submission:
inf = 10**18
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
dp = [[inf]*(N+1) for _ in range(H+1)]
for h in range(H+1):
    for i in range(N+1):
        if i > 0 and h - AB[i - 1][0] > 0:
            dp[h][i] = min(dp[h][i-1], dp[h-AB[i-1][0]][i] + AB[i-1][1])
        elif i > 0:
            dp[h][i] = min(dp[h][i-1], AB[i-1][1])

print(dp[H][N])
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7

lcm = a[0]
for i in range(1,n):
    lcm = lcm*a[i]//gcd(lcm,a[i])

ans = 0
for i in range(n):
    ans += lcm//a[i]
    ans %= mod

print(ans)

Fixed submission:
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7

lcm = a[0]
for i in range(1,n):
    lcm = lcm*a[i]//gcd(lcm,a[i])

lcm %= mod

ans = 0
for i in range(n):
    ans += pow(a[i],mod-2,mod)
    ans %= mod
ans *= lcm
ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
data=[list(inout().split()) for _ in range(n)]
s = input()
ans = 0
c = False
for i in range(n):
  if c:
    ans += int(data[i][1])
  if data[i][0] == s:
    c = True
print(ans)

Fixed submission:
n = int(input())
data=[list(input().split()) for _ in range(n)]
s = input()
ans = 0
c = False
for i in range(n):
   if c:
      ans += int(data[i][1])
   if data[i][0] == s:
      c = True
print(ans)
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort()
f.sort()
ok = max(a)*max(f)
ng = -1

while ok-ng > 1:
    mid = (ok+ng)//2
    t = 0
    for i in range(n):
        t += max(0,a[i]-int(mid/f[i]))
    if t > k:
        ng = mid
    else:
        ok = mid

print(ok)

Fixed submission:
a,b = map(int,input().split())
if a <10 and b < 10:
    print(a*b)
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
########ワーシャルフロイド法

def warshall_floyd(d):
    # d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


##############################
n, w, L = map(int, input().split())  # n:頂点数　w:辺の数

d = [[float("inf") for i in range(n)] for _ in range(n)]
# d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0  # 自身のところに行くコストは０
d = warshall_floyd(d)

D = [[float("inf") for i in range(n)] for i in range(n)]

for i in range(n):
    for j in range(n):
        if i == j:
            D[i][j] = 0
        elif d[i][j] <= L:
            D[i][j] = 1
            D[j][i] = 1

D = warshall_floyd(D)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if D[s][t] == float("inf"):
        print(-1)
    else:
        print(D[s][t] - 1)

Fixed submission:
def Warshall_Floyd(dist,n,restoration=False):
    next_point = [[j for j in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if dist[j][k] > dist[j][i] + dist[i][k]:
                    next_point[j][k] = next_point[j][i]
                    dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])
    if restoration:
        return dist,next_point
    else:
        return dist

n,m,l = map(int,input().split())
inf = 10**18
dist = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
    dist[i][i] = 0

for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    if c <= l:
        dist[a][b] = c
        dist[b][a] = c

dist = Warshall_Floyd(dist,n)
route = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            route[i][j] = 0
        elif dist[i][j] <= l:
            route[i][j] = 1

route = Warshall_Floyd(route,n)

q = int(input())


for i in range(q):
    s,t = map(int,input().split())
    s -= 1
    t -= 1
    print(route[s][t]-1 if route[s][t] < inf else -1)