Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
#        xi=xi%(bin(xi).count("1"))
        xi=xi%popcount(xi)
    print(icnt)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)
### BUGGY CODE ###

import bisect

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

A_B = []
B_C = []
total = 0

for a in A:
    k = bisect.bisect_right(B, a)
    l = N - k
    A_B.append(l)

for b in B:
    k = bisect.bisect_right(C, b)
    l = N - k
    B_C.append(l)

for n in range(N):
    total += sum(B_C[N-A_B[n]:])

print(total)



### FIXED CODE ###

import bisect

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

A_B = []
B_C = []
total = 0

for b in B:
    k = bisect.bisect_left(A,b)
    l = bisect.bisect_right(C,b)
    total += k * (N-l)

print(total)
### BUGGY CODE ###

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

m = n + 1
s = 0

for i in range(1,m):
    c = a.count(i)
    if c > 0:
        a.remove(i)
        print(c)
    else:
        print('0')


### FIXED CODE ###

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

s = [0]*(n)

for i in range(n-1):
    s[a[i]-1] = s[a[i]-1] + 1
    
for j in range(n):
    print(s[j])
### BUGGY CODE ###

import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = list(map(neg, high)), list(map(neg, low))
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]

factor = 2 ** n0
lsums = Counter([0])
for v in low:
    tmps = tuple(lsums.items())
    for u, cnt in tmps:
        lsums[u + v] += cnt
del lsums[0]
ans = 0
for lsum, cnt in lsums.items():
    tmp = 0
    q = deque()
    q.append((0, lsum))
    while len(q) > 0:
        i, v = q.popleft()
        if i + 1 < len(high) and v + acc[i + 1] >= 0:
            q.append((i + 1, v))
        if i >= len(high):
            continue
        v += high[i]
        if v == 0:
            tmp += 1
            continue
        if v < 0:
            q.append((i + 1, v))
    ans += tmp * cnt

ans *= factor
ans += 2 ** n0 - 1

print(ans)

### FIXED CODE ###

import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = list(map(neg, xs[:l][::-1])), r - l, xs[r:]

def sums(arr):
    cntr = Counter([0])
    for v in arr:
        tmps = tuple(cntr.items())
        for u, cnt in tmps:
            cntr[u + v] += cnt
    del cntr[0]
    return cntr

lsums = sums(low)
hsums = sums(high)

ans = sum(hsums[a] * b for a, b in lsums.items())

ans *= 2 ** n0
ans += 2 ** n0 - 1

print(ans)
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append([0 if i == "#" else H+W for i in list(input())])
a = np.array(b)

for i in range(1, H):
    a[i:, :] = np.minimum(a[i:, :], a[i-1:-1, :] + 1)
for i in range(H - 1, 0, -1):
    a[:i, :] = np.minimum(a[:i, :], a[1:i+1, :] + 1)
for j in range(1, W):
    a[:, j:] = np.minimum(a[:,j:], a[:, j-1:-1] + 1)
for j in range(W -1, 0, - 1):
    a[:, :j] = np.minimum(a[:, :j], a[:, 1:j+1] + 1)

print(np.max(a))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
a = [[0] * W for _ in range(H)]
q = deque([])
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            a[i][j] = 1
            q.appendleft((i, j, 0))

while True:
    try:
        i, j, val = q.pop()
        if i > 0 and a[i - 1][j] == 0:
            q.appendleft((i - 1, j, val + 1))
            a[i - 1][j] = 1
        if i < H - 1 and a[i + 1][j] == 0:
            q.appendleft((i + 1, j, val + 1))
            a[i + 1][j] = 1
        if j > 0 and a[i][j - 1] == 0:
            q.appendleft((i, j - 1, val + 1))
            a[i][j - 1] = 1
        if j < W - 1 and a[i][j + 1] == 0:
            q.appendleft((i, j + 1, val + 1))
            a[i][j + 1] = 1
    except:
        print(val)
        break
### BUGGY CODE ###

from collections import deque

N,M = map(int,input().split())

table = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
#    print(a,b)
    table[a].append(b)
    table[b].append(a)

visited = [0]*N
visited[0] = 1
H = deque()
H.append(0)
ans = 0
c = 1

while H:
    ans = max(ans,c)
    x = H.popleft()
#    print("x:",x,"c:",c)
#    print(visited)
    for y in table[x]:
        if visited[y] == 0:
            H.append(y)
            visited[y] = 1
#            print(y,"added")
            c += 1
    if not H:
        for i in range(N):
            if visited[i] == 0:
                H.append(i)
                visited[i] = 1
                c = 1
                break

print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self._size = [1]*N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_sama(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self._size[rb] += self._size[ra]
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
            self._size[ra] += self._size[rb]
        self.count += 1
    def print_info(self):
        print("parent", self.parent)
        print("rank", self.rank)
        print("count", self.count)
        print("size", self._size)
    def size(self,a):
        return self._size[self.root(a)]

N, M = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.unite(a,b)
ans = 0
for i in range(N):
    ans = max(ans,uf.size(i))
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
pos = [0, 0, 0]
for a in A:
  if a == 1:
    pos[0] += 1
  elif a == 2:
    pos[1] += 1
  elif a == 3:
    pos[2] += 1


dp = [[[0]*(N+1) for y in range(N+1)] for x in range(N+1)]


def get_expectation(pos):
  global dp
  px, py, pz = pos
  if px == py == pz == 0:
    return 0
  elif px<0 or px>N or py<0 or py>N or pz<0 or pz>N:
    return 0
  else:
    if dp[px][py][pz] > 0:
      return dp[px][py][pz]
    else:
      transition = [[1, 0, 0, 0], [-1, 1, 0, 1], [0, -1, 1, 2]]
      for dx, dy, dz, idx in transition:
        s = px + py + pz
        dp[px][py][pz] += (get_expectation([px-dx, py-dy, pz-dz]) + N/s)*[px, py, pz][idx]/s
      
      return dp[px][py][pz]


print(get_expectation(pos))

### FIXED CODE ###

N = int(input())
A = input().split()
px = py = pz = 0
for a in A:
  if a == '1':
    px += 1
  elif a == '2':
    py += 1
  elif a == '3':
    pz += 1

nx = px + py + pz
ny = py + pz
nz = pz

dp = [[[0]*(nx+1) for y in range(ny+1)] for z in range(nz+1)]

for z in range(nz+1):
  for y in range(ny+1-z):
    for x in range(nx+1-z-y):
      if x == y == z == 0:
        continue
      
      else:
        s = x + y + z
        t = N/s
        if x > 0:
          t += dp[z][y][x-1]*x/s
        if y > 0:
          t += dp[z][y-1][x+1]*y/s
        if z > 0:
          t += dp[z-1][y+1][x]*z/s
        
        dp[z][y][x] += t


print(dp[pz][py][px])
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())
a = [int(input())-1 for _ in range(n)]
#print(a)
cnt = 0
visit = [0] #出発点は訪れてる
i = 0
while True:
    cnt += 1
    #print(visit)
    if a[i] in visit:
        print(-1)
        exit()
    elif a[i] == 1:
        print(cnt)
        exit()
    else:
        visit.append(a[i])
        i = a[i]

### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
a = [int(input())-1 for _ in range(n)]
# -1をしたので、if a[s] == 1になったら終了
#print(a)
cnt = 0
visit = [0] #出発点は訪れてる
i = 0 # bottom position a[i] = next_bottom
while cnt <= n:#無限ループになる理由がわからん in が最悪のケースでO(nlogn)
    cnt += 1
    #print(visit)
    """if a[i] in visit:#循環するのでbreak
        print(-1)
        exit(0)"""
    if a[i] == 1: #ボタン２を押すので今までの回数を答える
        print(cnt)
        exit(0)
    else:# i を更新　visitに現在のボタンを追加する
        #visit.append(a[i])
        i = a[i]
print(-1)
### BUGGY CODE ###

q=int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
def primesFactraizar(n):
    is_prime = [True] * (n + 1) #まずは[1]*nを用意
    is_prime[0] = False 
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1): #素数の判定√nまでで十分
        if not is_prime[i]: #非素数は無視
            continue            #continue分はループ中の後続の命令をスキップする
        for j in range(i * 2, n + 1, i): #i*2~nまでのiの倍数を順番に消す
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
primes = primesFactraizar(10**5+1)

cumSum = [0]*(10**5+1)
tmp = 0
for i in range(10**5+1):
    if i in primes and (i+1)//2 in primes:
        tmp += 1 
    cumSum[i] = tmp


for l,r in lr:
    print(cumSum[r]-cumSum[l-1])

### FIXED CODE ###

q=int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
def primesFactraizar(n):
    is_prime = [True] * (n + 1) #まずは[1]*nを用意
    is_prime[0] = False 
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1): #素数の判定√nまでで十分
        if not is_prime[i]: #非素数は無視
            continue            #continue分はループ中の後続の命令をスキップする
        for j in range(i * 2, n + 1, i): #i*2~nまでのiの倍数を順番に消す
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
primes = primesFactraizar(10**5+1)

cumSum = [0]*(10**5+1)
tmp = 0
for i in range(10**5+1):
    if i in primes and (i+1)//2 in primes:
        tmp += 1 
    cumSum[i] = tmp


for l,r in lr:
    print(cumSum[r]-cumSum[l-1])
### BUGGY CODE ###

s = input()
q = int(input())

roll = False
ans = [s]
preNum = 0

for i in range(q) :
    inp = input()
    if inp[:1] == '1' :
        roll = not roll
        #print(roll)
    else :
        t, f, c = inp.split()
        #print(ans)
        #print(t, f, c)
        if (f == '1' and (not roll)) or (f == '2' and roll) :
            ans = ans[::-1]
            #print(ans, 'rev')
            ans.append(c)
            #print(ans, '+C')
            ans = ans[::-1]
            #print(ans, 'ver')
            preNum += 1
        else :
            ans.append(c)
#print(ans)
if roll :
    ans[preNum] = ans [preNum][::-1]
    ans = ans[::-1]

#print(ans)
#print("".join(ans))
for s in ans :
    print(s, end='')


### FIXED CODE ###

from collections import deque

s = input()
q = int(input())

roll = False
ans = deque([s])
preNum = 0

for i in range(q) :
    inp = input()
    if inp[:1] == '1' :
        roll = not roll
        #print(roll)
    else :
        t, f, c = inp.split()
        #print(ans)
        #print(t, f, c)
        if (f == '1' and (not roll)) or (f == '2' and roll) :
            ans.appendleft(c)
            preNum += 1
        else :
            ans.append(c)
#print(ans)
ans = list(ans)
if roll :
    ans[preNum] = ans[preNum][::-1]
    ans = ans[::-1]

#print(ans)
#print("".join(ans))
for s in ans :
    print(s, end='')
### BUGGY CODE ###

k,s = map(int,input().split())
a = 0

for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if x + y + z == s and 0 <= z <= k:
      a += 1

print(a)

### FIXED CODE ###

k,s = map(int,input().split())
a = 0

for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z <= k:
      a += 1

print(a)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
for i in range(n):
    print(np.count_nonzero(a == i + 1))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

c = Counter(a)
for i in range(n):
    print(c[i + 1])
### BUGGY CODE ###

def solve(n, a):
  if 0 in a:
    return 0
  else:
    p = 1
    x = 10**18
    for i in a:
      p*=i
    if p>x:
      p = -1
    return p

n = int(input())
a = [int(x) for x in input().split()]
print(solve(n, a))

### FIXED CODE ###

def solve(n, a):
  if 0 in a:
    return 0
  else:
    p = 1
    x = 10**18
    for i in a:
      if p<=x:
      	p*=i
      else:
        break
    if p>x:
      p = -1
    return p

n = int(input())
a = [int(x) for x in input().split()]
print(solve(n, a))
### BUGGY CODE ###

s = raw_input()
n = 0

def mul(s):
    if len(s) < 3:
        return 0
    n = 0
    _res = 0
    j = 0
    while j <= (len(s) - 2):
        j = j + _res
        if j < 0:
            j = 0
        _res = 0
        str = s[j:(j + 3)]
        if str == "ABC":
            n = n + 1
            _res = -2
            s = s[:j] + "BCA" + s[j + 3:]
        j = j + 1
    return n
print mul(s)

### FIXED CODE ###

def test(s):

	res = 0
	aAdd = 0
	last = ''
	tmp = ''
	for i in xrange(len(s)):
		if tmp and tmp > i:
			continue
		if s[i] == 'A':
			aAdd += 1
		elif s[i:i+2] == 'BC':
			# print aAdd
			res = res + aAdd
			tmp = i + 2
		else:
			aAdd = 0
			last = s[i]


	return res
s=raw_input()
print test(s)
### BUGGY CODE ###

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

now = 1

x = 2
while P >= x ** N:
    while P % (x ** N) == 0:
        now *= x
        P = P / (x ** N)
    while P % x == 0:
        P = P / x
    x += 1

print(now)

### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, round(p**(1/n))+1):
        if p % i**n ==0:
            res = i
    print(res)
### BUGGY CODE ###

target, m = map(int, input().split())

ship_count = 1
next_ships = []
next_start = []
for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    next_start.append(b)
  else:
    if b == target:
      next_ships.append([a, b])

if len(next_start) == 0:
  print('IMPOSSIBLE')
  exit(0)

for i in next_ships:
  a, b = i[0], i[1]
  if a in next_start:
    print('POSSIBLE')
    exit(0)

print('IMPOSSIBLE')


### FIXED CODE ###

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

s = []
e = []
for _ in range(m):
  a, b = map(int, input().split())
  if a == 1:
    s.append(b)
  if b == n:
    e.append(a)

if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

n, x = map(int, input().split())
a = list(map(int, input().split()))
a += a
ans = float("inf")
for i in range(1, n+1):
    t = 0
    for j in range(n):
        t += min(a[j:j + i])
    ans = min(ans, t+10*(i-1))
print(ans)

### FIXED CODE ###

n, x = map(int, input().split())
a = list(map(int, input().split()))
a += a
mah = [10000000000]*n
ans = float("inf")
for i in range(1, n+1):
    t = 0
    for j in range(n):
        if mah[j] > a[j + i]:
            mah[j] = a[j+i]
        t += mah[j]
    ans = min(ans, t+x*(i-1))
print(ans)
### BUGGY CODE ###


import numpy as np
N = int(input())
P = np.array([np.array([int(i) for i in input().split(' ')]) for j in range(N)]) 
Distance = [] 
for i in range(N):
    Distance.append([])
    for j in range(N):
        Distance[i].append(min(abs(P[i][0]-P[j][0]), abs(P[i][1]-P[j][1])))
NC = [i for i in range(1, N)]
C = [0]
disSum = 0
while len(NC) > 0:
    minDis = 1000000000
    for c in C:
        for t in NC:
            dis = Distance[c][t]
            if dis < minDis:
                nearest = t
                minDis = dis
#                 print(c,nearest,minDis)
    C.append(nearest)
    NC.remove(nearest)
    disSum += minDis
#     print(C)
#     print(NC)
print(disSum)

### FIXED CODE ###


import sys
sys.setrecursionlimit(int(2e9))

def distance(P, p1, p2):
    return min(abs(P[p1][1]-P[p2][1]), abs(P[p1][2]-P[p2][2]))
def root(CI, p):
    if CI[p] == p:
        return p
    else:
        CI[p] = root(CI, CI[p])
        return CI[p] 

N = int(input())
P = [[j]+[int(i) for i in input().split(' ')] for j in range(N)]
sortX = sorted(P,key=lambda x:x[1])
sortY = sorted(P,key=lambda x:x[2])
EX = [[sortX[i][0], sortX[i+1][0], distance(P,sortX[i][0],sortX[i+1][0])] for i in range(N-1)]
EY = [[sortY[i][0], sortY[i+1][0], distance(P,sortY[i][0],sortY[i+1][0])] for i in range(N-1)]
E = EX + EY
E = sorted(E, key=lambda x:x[2])
CI = [i for i in range(N)]
disSum = 0
for e in E:
    s,l = min(e[0],e[1]),max(e[0],e[1])
#     if CI[s] != CI[l]:
#         CI = list(map(lambda x:CI[s] if x == CI[l] else x, CI))
#         disSum += e[2]
    if root(CI, s) != root(CI, l):
        CI[root(CI, l)] = root(CI, s)
        disSum += e[2]
print(disSum)
### BUGGY CODE ###

n,m  =map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
ans = 0

for _ in range(m):
		a[n-1]=a[n-1]//2
		a.sort()

for i in range(n):
	ans+=a[i]

print(ans)


### FIXED CODE ###

import heapq

n,m = (int(x) for x in input().split())

a = [int(i)*(-1) for i in input().split()]
heapq.heapify(a)
for _ in range(m):

    b  = -(heapq.heappop(a))//2
    heapq.heappush(a,-b)


print(-sum(a))
### BUGGY CODE ###

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

Z = sum(sum(a) for a in A) + sum(sum(b) for b in B) + 10

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] = (1 << Z)

for h in range(H):
    for w in range(W):
        d = dp[h][w]
        k = abs(A[h][w] - B[h][w])

        dp[h + 1][w] |= (d << k) | (d >> k)
        dp[h][w + 1] |= (d << k) | (d >> k)

ans = 10**18
for a in (dp[H][W - 1], dp[H - 1][W]):
    for d in range(Z * 2 + 10):
        if a & (1 << d) != 0:
            ans = min(ans, abs(d - Z))
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
M = (H + W) * 80

A = [tuple(map(int, input().split())) for _ in range(H)]
B = [tuple(map(int, input().split())) for _ in range(H)]

dp = [[0] * W for _ in range(H)]
dp[0][0] = (1 << (M - abs(A[0][0] - B[0][0])))

for h in range(H):
    for w, (a, b) in enumerate(zip(A[h], B[h])):
        d = abs(a - b)
        mask = 0
        if h > 0:
            mask |= (dp[h - 1][w] << d)
            mask |= (dp[h - 1][w] >> d)
        if w > 0:
            mask |= (dp[h][w - 1] << d)
            mask |= (dp[h][w - 1] >> d)
        dp[h][w] |= mask

state = dp[-1][-1]
nums = []
for digit, b in enumerate(bin(state)[2:][:: -1]):
    if b == '1':
        nums.append(digit - M)
ans = min(abs(n) for n in nums)
print(ans)
### BUGGY CODE ###

from functools import reduce

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

res = reduce(lambda a, b: a*b, A)
if res > 10 ** 18:
    print(-1)
else:
    print(res)


### FIXED CODE ###

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

    if 0 in A:
        print(0)
        return

    res = 1
    for a in A:
        res *= a
        if res > 10 ** 18:
            print(-1)
            return
    print(res)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np

A,B,M = map(int,input().split())
a = input().split()
b = input().split()

num = 100000

for _ in range(M):
    m1,m2,m3 = map(int,input().split())
    for q in range(A):
        for w in range(B):
            res = int(a[q])+int(b[w])
            if q+1 == m1 and w+1 == m2: res-=m3
            num = min(num,res)
print(num)

### FIXED CODE ###

import numpy as np

A,B,M = map(int,input().split())
a = input().split()
b = input().split()

num = int(min(a)) + int(min(b))

for _ in range(M):
    m1,m2,m3 = map(int,input().split())
    res = int(a[m1-1])+int(b[m2-1]) - m3
    num = min(num,res)

print(num)
### BUGGY CODE ###

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

r = N
asum = [0]

for i in A:
    asum.append(asum[-1] + i)    

for i in range(len(A)):
    Axor = A[i]
    for j in range(i+1, len(A)):
        Axor = Axor ^ A[j]
        if (asum[j+1] - asum[i]) == Axor:
            r += 1
        else:
            break

print(r)

### FIXED CODE ###

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

res = 0
asum = [0]
axor = [0]

for i in A:
    asum.append(asum[-1] + i)
    axor.append(axor[-1] ^ i)

for l in range(N):
    ok = l+1
    ng = N+1
    while(ng - ok > 1):
        r = (ok + ng) // 2
        s = (axor[r] ^ axor[l])
        t = (asum[r] - asum[l])
        if s == t:
            ok = r
        else:
            ng = r
    
    res += ok - l
         
print(res)
### BUGGY CODE ###

N,M=map(int,input().split())

D={}
for _ in range(N):
    A,B=map(int,input().split())

    if A in D:
        D[A]+=B
    else:
        D[A]=B

L=[]
for m in D:
    L.append((m,D[m]))

L.sort(key=lambda x:x[0])

S=0
while M>0:
    (A,B)=L.pop(0)
    if B>=M:
        B=M
    S+=A*B
    M-=B
print(S)


### FIXED CODE ###

N,M=map(int,input().split())

D={}
for _ in range(N):
    A,B=map(int,input().split())

    if A in D:
        D[A]+=B
    else:
        D[A]=B

L=[]
for m in D:
    L.append((m,D[m]))

L.sort(key=lambda x:x[0])

S=0
I=0
while M>0:
    (A,B)=L[I]
    B=min(B,M)
    S+=A*B
    M-=B
    I+=1
print(S)
### BUGGY CODE ###

import sys
MAX_INT = sys.maxsize # 大きい値

H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

# print(AB)
dp = [ [MAX_INT]*(H+1) for _ in range(N+1) ]

for i in range(N):
    for j in range(H+1):
        if AB[i][0] > j:
            dp[i+1][j] = min(dp[i][j],AB[i][1])
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-AB[i][0]] + AB[i][1])

print(dp[N][H-1])

### FIXED CODE ###

import numpy as np
H,N = map(int,input().split())

a = np.empty(N,dtype='int')
b = np.empty(N,dtype='int')

# dp[i] ヒットポイントiの魔物を倒すのに必要な最小の魔力
dp = np.array([float('inf')]*(H+1))
dp[0] = 0

for i in range(N):
    a[i],b[i] = map(int,input().split())

# hがヒットポイント
for h in range(1,H+1):
    t = h - a
    t[t<0] = 0
    dp[h] = np.min(dp[t] + b)

print(int(dp[H]))