Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import numpy as np
n = int(input())
t = list(int(input()) for _ in range(n))

print(np.lcm.reduce(t))


Fixed submission:
from fractions import gcd
n = int(input())
t = list(int(input()) for _ in range(n))


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


ans = 1
for i in t:
    ans = lcm(ans, i)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a = list(map(int, input().split()))

if a[0] % 2 == 1 or a[1] % 2 == 1 or a[2] % 2 == 1:
    print(0)
    exit()
elif a[0] == a[1] == a[2]:
    print(-1)

cnt = 0
while True:
    a[0], a[1], a[2] = a[1]//2+a[2]//2, a[0]//2+a[2]//2, a[0]//2+a[1]//2
    cnt += 1
    for i in a:
        if i % 2 == 1:
            print(cnt)
            exit()

Fixed submission:
a = list(map(int, input().split()))

if a[0] % 2 == 1 or a[1] % 2 == 1 or a[2] % 2 == 1:
    print(0)
    exit()

cnt = 0
for _ in range(1000):
    for i in a:
        if i % 2 == 1:
            print(cnt)
            exit()
    a[0], a[1], a[2] = a[1] // 2 + a[2] // 2, a[0] // 2 + a[2] // 2, a[0] // 2 + a[1] // 2
    cnt += 1
else:
    print(-1)

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

if a[0] % 2 == 1 or a[1] % 2 == 1 or a[2] % 2 == 1:
    print(0)
    exit()
elif a[0] == a[1] == a[2]:
    print(-1)

cnt = 0
while True:
    a[0], a[1], a[2] = a[1]//2+a[2]//2, a[0]//2+a[2]//2, a[0]//2+a[1]//2
    cnt += 1
    for i in a:
        if i % 2 == 1:
            print(cnt)
            exit()

Fixed submission:
a = list(map(int, input().split()))

if a[0] % 2 == 1 or a[1] % 2 == 1 or a[2] % 2 == 1:
    print(0)
    exit()

cnt = 0
for _ in range(1000):
    for i in a:
        if i % 2 == 1:
            print(cnt)
            exit()
    a[0], a[1], a[2] = a[1] // 2 + a[2] // 2, a[0] // 2 + a[2] // 2, a[0] // 2 + a[1] // 2
    cnt += 1
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, c = map(int, input().split())

i = 1
while a * i <= 10 ** 10:
    if (a * i) % b == c:
        print("YES")
        exit()
    i += 1

print("NO")

Fixed submission:
a, b, c = map(int, input().split())

i = 1
while a * i <= b ** 2:
    if (a * i) % b == c:
        print("YES")
        exit()
    i += 1

print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
import math
n  = int(input())
 
ans = 1
for i in range(1, n+1):
  ans *= i
 
s = 10**9 + 7
 
print(ans % s)

Fixed submission:
import math
n  = int(input())
 
ans = math.factorial(n)
 
s = 10**9 + 7
 
print(ans % s)

Buggy python submission (verdict: Runtime Error):
import math
n  = int(input())
 
ans = math.factional(n)
 
s = 10**9 + 7
 
print(ans % s)

Fixed submission:
import math
n  = int(input())
 
ans = math.factorial(n)
 
s = 10**9 + 7
 
print(ans % s)

Buggy python submission (verdict: Time Limit Exceeded):
n  = int(input())

ans = 1
for i in range(1, n+1):
  ans = ans * i

s = 10**9 + 7

print(ans % s)

Fixed submission:
import math
n  = int(input())
 
ans = math.factorial(n)
 
s = 10**9 + 7
 
print(ans % s)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ab = [list(map(int, input().split())) for i in range(n)][::-1]

ans = 0
for a, b in ab:
    tmp = a
    while tmp % b != 0:
        tmp += 1
    for i in range(n):
        ab[i][0] += tmp - a
    ans += tmp - a
print(ans)

Fixed submission:
n = int(input())
ab = [list(map(int, input().split())) for i in range(n)][::-1]

ans = 0
for a, b in ab:
    a += ans
    # 負の剰余。
    ans += -a % b
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()

ans = [0]
for i in range(1, n+1):
  if s[i] == "I":
    ans.append(ans[i-1]+1)
  else:
    ans.append(ans[i-1]-1)

print(max(ans))

Fixed submission:
n = int(input())
s = input()

ans = [0]
for i in range(n):
    if s[i] == "I":
        ans.append(ans[i] + 1)
    else:
        ans.append(ans[i] - 1)

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

l = set()
for i in range(k+1):
    for j in range(k+1):
        if i+j+k >= s and s-i-j >= 0:
            l.add((i, j, s-i-j))
        else:
            continue

print(len(l))

Fixed submission:
k, s = map(int, input().split())

count = 0
for i in range(k+1):
    for j in range(k+1):
        if i+j+k >= s and s-i-j >= 0:
            count += 1
        else:
            continue

print(count)
Buggy python submission (verdict: Runtime Error):
n = int(input())
t = list(map(int, input().split()))
m = int(input())

for _ in range(m):
    temp = t.copy()
    p, x = map(int, input().split())
    temp[p-1] = x
    print(sum(temp))

Fixed submission:
import copy

n = int(input())
t = list(map(int, input().split()))
m = int(input())

for _ in range(m):
    temp = copy.copy(t)
    p, x = map(int, input().split())
    temp[p-1] = x
    print(sum(temp))
Buggy python submission (verdict: Time Limit Exceeded):
import re
s = input()
s = s[::-1]

for i in range(len(s)//5):
    s = re.sub("^remaerd", "", s)
    s = re.sub("^maerd", "", s)
    s = re.sub("^resare", "", s)
    s = re.sub("^esare", "", s)

if s == "":
    print("YES")
else:
    print("NO")

Fixed submission:
s = input()

while True:
    for word in ["dream", "dreamer", "erase", "eraser"]:
        if s.endswith(word):
            s = s[:-len(word)]
            break
    else:
        print("NO")
        exit()
    if s == "":
        print("YES")
        break

Buggy python submission (verdict: Time Limit Exceeded):
import re
s = input()
s = s[::-1]

for i in range(len(s)):
    s = re.sub("^remaerd", "", s)
    s = re.sub("^maerd", "", s)
    s = re.sub("^resare", "", s)
    s = re.sub("^esare", "", s)

if s == "":
    print("YES")
else:
    print("NO")

Fixed submission:
s = input()

while True:
    for word in ["dream", "dreamer", "erase", "eraser"]:
        if s.endswith(word):
            s = s[:-len(word)]
            break
    else:
        print("NO")
        exit()
    if s == "":
        print("YES")
        break
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()
t = input()

for i in range(n):
    if s[i:] == t[:n-i]:
        print(n + cnt)
        exit()
else:
    print(n*2)

Fixed submission:
n = int(input())
s = input()
t = input()

ans = len(s + t)
for i in range(n):
    if s[i:] == t[:n-i]:
        print(n+i)
        exit()
print(n*2)
Buggy python submission (verdict: Time Limit Exceeded):
x = input()

length = len(x)
while True:
    x = x.replace("ST", "")
    if len(x) == length:
        break
    else:
        length = len(x)

print(len(x))

Fixed submission:
x = input()

pair_cnt = 0
s_cnt = 0
for i in x:
    if i == "S":
        s_cnt += 1
    elif i == "T" and s_cnt:
        pair_cnt += 1
        s_cnt -= 1

print(len(x) - pair_cnt * 2)
Buggy python submission (verdict: Time Limit Exceeded):
a, b = map(int, input().split())

if a <= 0 <= b:
    print("Zero")
    exit()

minus = 0
for i in range(a, b+1):
    if i < 0:
        minus += 1

print("Positive" if minus % 2 == 0 else "Negative")

Fixed submission:
a, b = map(int, input().split())

if a <= 0 <= b:
    print("Zero")
    exit()

if a < 0 and b < 0:
    print("Positive" if (b - a + 1) % 2 == 0 else "Negative")
    exit()

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

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
for i in range(m+1):
    f=pow(2,i)
    p=pow(x,f,m)
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)


Fixed submission:
n,x,m=map(int,input().split())

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
p=x
for i in range(m+1):
    if i!=0: p=p*p%m
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)

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

f=1
w=[]
d=set([])
t=[0]
chk=n
#while 1:
for i in range(m+1):
    f=pow(2,i)
    p=pow(x,f,m)
    if p in d: break
    d.add(p)
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)


Fixed submission:
n,x,m=map(int,input().split())

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
p=x
for i in range(m+1):
    if i!=0: p=p*p%m
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)

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

f=1
w=[]
d=set([])
t=[0]
chk=n
while 1:
    p=pow(x,f,m)
    if p in d: break
    d.add(p)
    w.append(p)
    t.append(t[-1]+p)
    f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)


Fixed submission:
n,x,m=map(int,input().split())

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
p=x
for i in range(m+1):
    if i!=0: p=p*p%m
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod=1000000007
n=int(input())
#n,k=map(int,input().split())
a=[int(i) for i in input().split()]
ans=chk=0
for i in range(n-1):
    for j in range(i+1,n):
        ans+=(a[i]*a[j])%mod
        ans%=mod
print(ans)

Fixed submission:
mod=1000000007
n=int(input())
#n,k=map(int,input().split())
a=[int(i) for i in input().split()]
t=[0]*(n+1)
for i in range(n):
    t[i]=t[i-1]+a[i]
ans=chk=0
#print(t)
for i in range(n-1):
#    print(-(i+1))
    x=-1*(i+1)
#    print(x)
#    print(a[x],t[x-2])
    ans+=a[x]*t[x-2]
    ans%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
d={}
for i in range(1,100):
    for j in range(i,100):
        if i**2>n or j**2>n: break
        for k in range(j,100):
            tmp=i**2+j**2+k**2+i*j+j*k+k*i
            if tmp>n: break
            if i==k: x=1
            elif i==j or j==k: x=3
            else: x=6
            if tmp in d: d[tmp]+=x
            else: d[tmp]=x
for i in range(1,n+1):
    if i in d: print(d[i]

Fixed submission:
n=int(input())
d={}
for i in range(1,100):
    if i**2>n: break
    for j in range(i,100):
        if j**2>n: break
        for k in range(j,100):
            tmp=i**2+j**2+k**2+i*j+j*k+k*i
            if tmp>n: break
            if i==k: x=1
            elif i==j or j==k: x=3
            else: x=6
            if tmp in d:
                d[tmp]+=x
            else:
                d[tmp]=x
for i in range(1,n+1):
    if i in d: print(d[i])
    else: print(0)

Buggy python submission (verdict: Time Limit Exceeded):
def sol():
    n=int(input())

    def col(n):
        ans=chk=0
        for i in range(1,n):
            if i**2>=n: break
            for j in range(1,n):
                if j**2>=n: break
                for k in range(1,n):
                    if k**2>=n: break
                    if i**2+j**2+k**2+i*j+j*k+k*i==n: ans+=1
        return ans
    for i in range(1,n+1):
        print(col(i))

if __name__=="__main__":
    sol()


Fixed submission:
n=int(input())
d={}
for i in range(1,100):
    if i**2>n: break
    for j in range(i,100):
        if j**2>n: break
        for k in range(j,100):
            tmp=i**2+j**2+k**2+i*j+j*k+k*i
            if tmp>n: break
            if i==k: x=1
            elif i==j or j==k: x=3
            else: x=6
            if tmp in d:
                d[tmp]+=x
            else:
                d[tmp]=x
for i in range(1,n+1):
    if i in d: print(d[i])
    else: print(0)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())

def col(n):
    ans=chk=0
    for i in range(1,n):
        if i**2>=n: break
        for j in range(1,n):
            if j**2>=n: break
            for k in range(1,n):
                if k**2>=n: break
                if i**2+j**2+k**2+i*j+j*k+k*i==n: ans+=1
    return ans
for i in range(1,n+1):
    print(col(i))


Fixed submission:
n=int(input())
d={}
for i in range(1,100):
    if i**2>n: break
    for j in range(i,100):
        if j**2>n: break
        for k in range(j,100):
            tmp=i**2+j**2+k**2+i*j+j*k+k*i
            if tmp>n: break
            if i==k: x=1
            elif i==j or j==k: x=3
            else: x=6
            if tmp in d:
                d[tmp]+=x
            else:
                d[tmp]=x
for i in range(1,n+1):
    if i in d: print(d[i])
    else: print(0)
Buggy python submission (verdict: Time Limit Exceeded):
def mdiv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

n=int(input())
ans=chk=0
for i in range(1,n+1):
    ans+=i*len(mdiv(i))
print(ans)


Fixed submission:
n=int(input())
ans=0
for i in range(1,n+1):
    m=n//i*i
    k=n//i
    ans+=(k*(i+m)//2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[int(i) for i in input().split()]
ans=1
for i in a:
    ans*=i

print(ans if ans<=10**18 else -1)


Fixed submission:
n=int(input())
a=[int(i) for i in input().split()]
if 0 in a:
    print(0)
    exit()
a.sort(reverse=True)
ans=1
x=10**18
for i in a:
    ans*=i
    if ans>x:
        print(-1)
        exit()

print(ans)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
if (a[0]==1):
    print(1)
    exit()
ans=chk=0
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
p=w.index(t)
if p==0:
    print(w[k%len(w)])
else:
    print(h[0])


Fixed submission:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d=[0]
w=set([0])
x=0
for i in range(n):
    if a[x]-1 not in w:
        d.append(a[x]-1)
        w.add(a[x]-1)
        x=a[x]-1
    else:
        f=a[x]-1
        break

#print(d)
if k<len(d):
    print(d[k]+1)
else:
    x=k-len(d)
    y=d.index(f)
    z=len(d)-y
    #print(d,f,x,y,z)
    #exit()
    print(d[y+x%z]+1)

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
if (a[0]==1):
    print(1)
    exit()
ans=chk=0
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
p=w.index(t)
if p==0:
    print(w[len(w)%k-1])
else:
    print(h[0])


Fixed submission:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d=[0]
w=set([0])
x=0
for i in range(n):
    if a[x]-1 not in w:
        d.append(a[x]-1)
        w.add(a[x]-1)
        x=a[x]-1
    else:
        f=a[x]-1
        break

#print(d)
if k<len(d):
    print(d[k]+1)
else:
    x=k-len(d)
    y=d.index(f)
    z=len(d)-y
    #print(d,f,x,y,z)
    #exit()
    print(d[y+x%z]+1)

Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
ans=chk=0
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
    if i==k-1:
        print(t)
        exit()
mae=max(0,w.index(t)-1)
k-=mae
loop=len(w)-mae-1
print(w[k%loop+mae])


Fixed submission:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d=[0]
w=set([0])
x=0
for i in range(n):
    if a[x]-1 not in w:
        d.append(a[x]-1)
        w.add(a[x]-1)
        x=a[x]-1
    else:
        f=a[x]-1
        break

#print(d)
if k<len(d):
    print(d[k]+1)
else:
    x=k-len(d)
    y=d.index(f)
    z=len(d)-y
    #print(d,f,x,y,z)
    #exit()
    print(d[y+x%z]+1)

Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d=[0]
w=set([0])
x=0
for i in range(n):
    if a[x]-1 not in w:
        d.append(a[x]-1)
        w.add(a[x]-1)
        x=a[x]-1
    else:
        f=a[x]-1
        break

#print(d)
if k<len(d):
    print(d[k])
else:
    x=k-len(d)
    y=d.index(d[f])
    z=len(d)-y+1
    #print(d,y)
    #exit()
    print(d[y+x%z]+1)


Fixed submission:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d=[0]
w=set([0])
x=0
for i in range(n):
    if a[x]-1 not in w:
        d.append(a[x]-1)
        w.add(a[x]-1)
        x=a[x]-1
    else:
        f=a[x]-1
        break

#print(d)
if k<len(d):
    print(d[k]+1)
else:
    x=k-len(d)
    y=d.index(f)
    z=len(d)-y
    #print(d,f,x,y,z)
    #exit()
    print(d[y+x%z]+1)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,n=map(int,input().split())

ans=0
t=min(b,n)
for i in range(t,min(t-3,-1),-1):
    ans=max(ans,((a*i)//b-(a*(i//b))))
print(ans)


Fixed submission:
a,b,n=map(int,input().split())

ans=0
t=min(b,n)
for i in range(t,max(t-3,-1),-1):
    ans=max(ans,((a*i)//b-(a*(i//b))))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
a,b,n=map(int,input().split())

ans=0
for i in range(n+1):
    ans=max(ans,((a*i)//b-(a*(i//b))))
print(ans)


Fixed submission:
a,b,n=map(int,input().split())

ans=0
t=min(b,n)
for i in range(t,max(t-3,-1),-1):
    ans=max(ans,((a*i)//b-(a*(i//b))))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
for i in range(a):
    for j in range(i,b):
        ans=min(ans,A[i]+B[j])
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)


Fixed submission:
a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
ans=min(A)+min(B)
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)

Buggy python submission (verdict: Runtime Error):
a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
for i in range(a):
    for j in range(i,b)::
        ans=min(ans,A[i]+B[j])
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)


Fixed submission:
a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
ans=min(A)+min(B)
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
for i in A:
    for j in B:
        ans=min(ans,i+j)
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)

Fixed submission:
a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
ans=min(A)+min(B)
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)

Buggy python submission (verdict: Runtime Error):
a,b,m=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]

ans=99999999999
for i a:
    for j in b:
        ans=min(ans,i+j)
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,a[x-1]+b[y-1]-c)
print(ans)


Fixed submission:
a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
ans=min(A)+min(B)
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

n=input()
x=len(n)
k=int(input())
l=[int(i) for i in n]
dp1=[[0]*(k+2) for i in range(x+1)]
dp2=[[0]*(k+2) for i in range(x+1)]
dp2[0][0]=1
dp2[1][0]=1
dp2[1][1]=l[0]-1
for i in range(1,k+1):
    dp1[i][i]=1
for i in range(k,x+1):
    dp1[i][k]=1
for i in range(2,x+1):
    for j in range(k+1):
        if j==0:
            dp2[i][j]=1
        elif j<=i:
            dp2[i][j]+=max(0,l[i-1]-1)
            dp2[i][j]+=((dp2[i-1][j])+(dp2[i-1][j-1]*9))
            #print(i,j,dp2[i-1][j],dp2[i-1][j-1]*9)
print(dp1[x][k]+dp2[x][k])

Fixed submission:
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]

## dp1:top   dp2:under
dp1=[[0]*(k+2) for i in range(x)]
dp2=[[0]*(k+2) for i in range(x)]

dp1[0][0]=1
dp1[0][1]=0
dp2[0][0]=0
dp2[0][1]=0

cnt=0
for i in range(1,x):
    if l[i]>0:
        cnt+=1
    if cnt<=k:
        dp1[i][cnt]=1
for i in range(1,x):
    for j in range(k+1):
        if j==0:
            dp2[i][0]=1
        else:
            if l[i]==0: dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))
            else: dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))+(dp1[i-1][j])
print(dp1[-1][-2]+dp2[-1][-2])
Buggy python submission (verdict: Time Limit Exceeded):
def sol():
    h,n=map(int,input().split())
    l=[]
    ans=0
    for i in range(n):
        a,b=map(int,input().split())
        l.append((a,b))
    d=[0]*20005
    for i in range(h):
        for j in l:
            a,b=j[0],j[1]
            x=d[i]+b
            if i==0 or (d[i]!=0 and d[i+a]==0):
                if d[i+a]==0:
                    d[i+a]=x
                else:
                    d[i+a]=min(d[i+a],x)
            elif d[i]!=0 and d[i+a]!=0:
                d[i+a]=min(d[i+a],x)

    for i in range(h,20005):
        if ans==0:
            ans=d[i]
        elif d[i]!=0:
            ans=min(ans,d[i])
    print(ans)

if __name__=="__main__":
    sol()


Fixed submission:
def sol():
    h,n=map(int,input().split())
    l=[]
    ans=0
    for i in range(n):
        a,b=map(int,input().split())
        l.append((a,b))
    d=[0]*20005
    for i in range(h):
        for j in l:
            a,b=j[0],j[1]
            x=d[i]+b
            if i==0 or (d[i]!=0 and d[i+a]==0):
                if d[i+a]==0:
                    d[i+a]=x
                else:
                    d[i+a]=min(d[i+a],x)
            elif d[i]!=0 and d[i+a]!=0:
                d[i+a]=min(d[i+a],x)

    for i in range(h,20005):
        if ans==0:
            ans=d[i]
        elif d[i]!=0:
            ans=min(ans,d[i])
    print(ans)

if __name__=="__main__":
    sol()