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

import sys
sys.setrecursionlimit(10**7)

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

memo = [-1] * (k+1)
def rec(x):
    if memo[x] >= 0:
        return memo[x]
    flag = 0
    for i in range(n):
        if x - a[i] < 0:
            continue
        if rec(x - a[i]) == 0:
            flag = 1
    if flag == 1:
        memo[x] = 1
        return 1
    else:
        memo[x] = 0
        return 0

if rec(k) == 1:
    print("First")
else:
    print("Second")

### FIXED CODE ###

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

dp = [0] * (k+1)

for i in range(1, k+1):
    for a in A:
        if i - a < 0:
            break
        if dp[i-a] == 0:
            dp[i] = 1

if dp[k] == 1:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

import sys
n,k = map(int, sys.stdin.readline().rstrip("\n").split())
a = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
kmt = []
p = 1
for i in range(k):
    p *= a[i]
kmt.append(p)
for i in range(k,n):
    p = p * a[i] // a[i-k]
    kmt.append(p)
i = 0
while i+1< len(kmt):
    if kmt[i] < kmt[i+1]:
        print('Yes')
    else:
        print('No')
    i += 1

### FIXED CODE ###

import sys
n,k = map(int, sys.stdin.readline().rstrip("\n").split())
a = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
p = 1
for i in range(k,n):
    if a[i-k] < a[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def main():
    from decimal import Decimal
    import sys
    readline = sys.stdin.readline

    n = int(readline())
    *p, = (Decimal(pi) for pi in readline().rstrip().split())

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    # dp[投げた枚数][表の枚数] = 確率

    for i, pi in enumerate(p, 1):
        for j in range(i + 1):
            dp[i][j] += dp[i - 1][j] * (1 - pi) + dp[i - 1][j - 1] * pi

    ret = sum(dp[n][j] for j in reversed(range(n + 1)) if j * 2 > n)
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
p = tuple(map(float, input().split()))

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

for i in range(1, N + 1):
    for j in range(i + 1):
        dp[i][j] = (dp[i - 1][j] * (1 - p[i - 1])) + (dp[i - 1][j - 1] * p[i - 1])

ans = 0
for j in range(N // 2 + 1, N + 1):
    ans += dp[N][j]
print(ans)
# print(dp)
### BUGGY CODE ###

from collections import defaultdict
N=int(input())
ss = []
for i in range(N):
  ss.append(input())
d = defaultdict(lambda: 0)

for i in range(N):
  s = ss[i]
  d[s] += 1

d_ =[k for k, v in d.items() if v == max(d.values())]
d_.sort()
print("\n".join(d_))

### FIXED CODE ###

from collections import defaultdict
import collections
N=int(input())
ss = []
for i in range(N):
  ss.append(input())
#d = defaultdict(lambda: 0)
c = collections.Counter(ss)
d_=c.most_common()
mx = d_[0][1]
d_.sort()
#print(d_)
m=len(d_)
for i in range(m):
  if d_[i][1] == mx:
    print(d_[i][0])
  else:
    pass
### BUGGY CODE ###

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

for x in range(1,N+1):
    m = A.index(x) + 1
    B.append(str(m))
print(" ".join(B))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0] * (N +1)

for i in range(N):
    B[A[i]] = i+1

print(*B[1:])
### BUGGY CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


h, w = map(int, input().split())
a = [input() for _ in range(h)]
ans = bfs(a)
print(max(max(ansi) for ansi in ans))


### FIXED CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return dist[x][y]


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(bfs(a))
### BUGGY CODE ###

N,K = map(int,input().split())
L = list(map(int,input().split()))
L = sorted(L,reverse=False)

ans = "IMPOSSIBLE"
if L[-1] < K :
    ans = "IMPOSSIBLE"
elif (K in L) or (1 in L) : 
    ans = "POSSIBLE"
else :
    for i in range(1,N) :
        if L[i] % L[0] != 0 :
            ans = "POSSIBLE"
            break

for i in range(N) :
    if (K + L[i]) in L :
        ans = "POSSIBLE"

print(ans)


### FIXED CODE ###

def gcd(a,b) :
    while b :
        a,b = b, a % b
    return a

N,K = map(int,input().split())
L = list(map(int,input().split()))

if len(L) == 1 :
    if L[0] == K :
        ans = "POSSIBLE"
    else :
        ans = "IMPOSSIBLE"

else :
    for i in range(N-1) :
        q = gcd(L[i],L[i+1])
        if i == 0 :
            p = gcd(L[i],L[i+1])
        if q < p :
            p = q

    if (K % p ==  0) and (K <= max(L)) :
        ans = "POSSIBLE"
    else :
        ans = "IMPOSSIBLE"
print(ans)
### BUGGY CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))
L=x+[X]
if N==1:
	print(abs(X-x[0]))
else:
	LL=[abs(L[i+1]-L[i]) for i in range(N)]
	M=min(LL)
	while any([l%M!=0 for l in LL]):
		M=M-1
	print(M)

### FIXED CODE ###

from functools import reduce
N,X=map(int,input().split())
x=list(map(int,input().split()))
L=x+[X]
if N==1:
	print(abs(X-x[0]))
else:
	LL=[abs(L[i+1]-L[i]) for i in range(N)]
	def gcd(a,b):
		while b>0:
			a,b=b,a%b
		return a
	print(reduce(gcd,LL))
### BUGGY CODE ###

class Hash:
    def __init__(self):
        self.size = 1000000
        self.l = [0] * 1000000

    def insert_key(self, st):
        i = 0
        while True:
            j = self.h(st, i)
            if self.l[j] == 0:
                self.l[j] = st
                #print("inserted")
                return
            else:
                i = i+1

    def find_key(self, st):
        i = 0
        while True:
            j = self.h(st, i)
            if self.l[j] == st:
                return "yes"
            elif self.l[j] == 0 or (i >= self.size):
                return "no"
            else:
                i += 1

    def h1(self, key):
        return sum([ord(c) for c in key]) % self.size

    def h2(self, key):
        return 1 + sum([ord(c) for c in key]) % ( self.size - 1 )

    def h (self, key, i):
        return (self.h1(key) + i* self.h2(key)) % self.size

#main
n = int(input())
hash = Hash()

for _ in range(n):
    ope, st = input().split()
    if ope == "insert":
        hash.insert_key(st)
    elif ope == "find":
        print(hash.find_key(st))

### FIXED CODE ###

dic ={}


n = int(input())

for _ in range(n):
    com, word = input().split()
    
    if com =="insert":
        dic[word] = True
    elif com =='find':
        print("yes" if word in dic else "no")
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
Amax = max(a)
for i in range(n):
    if Amax > a[i]:
        print(Amax)
    else:
        print(sorted(a)[-2])

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
Amax = max(a)
Amax2 = sorted(a)[-2]
for i in range(n):
    if Amax > a[i]:
        print(Amax)
    else:
        print(Amax2)
### BUGGY CODE ###

n = int(input())

game = [[] for i in range(n)]

for i in range(n):
    game[i] = list(map(int,input().split()))

index = [0 for i in range(n)]
days = 0
finish = 0
tot = (n*(n-1))//2
flag = True
ok = True
tempok = False
while flag:
    tempok = False
    cant = set()
    for i in range(n):
        if i in cant:
            continue
        if index[i] >= n-1:
            continue
        vs = game[i][index[i]]
        vs -= 1
        if vs in cant:
            continue
        if game[vs][index[vs]]-1 == i:
            finish += 1
            index[i] += 1
            index[vs] += 1
            tempok = True
            cant.add(vs)
            cant.add(i)
            # print(i,vs)
        if finish >= tot:
            ok = True
            flag = False
            break
    if not tempok:
        ok = False
        break
    days += 1
    # print(finish)
    # print(tot)
    # print(days)
    # print(index)
    # print(game)

if not ok:
    print(-1)
else:
    print(days)


### FIXED CODE ###

def resolve():
    n = int(input())
    a = []

    for i in range(n):
        row = list(map(lambda x: int(x) - 1, input().split()))
        row.reverse()
        a.append(row)

    q = set()

    def check(i):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if i == a[j][-1]:
            p = (i, j) if i < j else (j, i)
            q.add(p)

    for i in range(n):
        check(i)

    day = 0
    while len(q) > 0:
        day += 1
        prev_q, q = q, set()

        for p in prev_q:
            (i, j) = p
            a[i].pop()
            a[j].pop()

        for p in prev_q:
            (i, j) = p
            check(i)
            check(j)

    for i in range(n):
        if len(a[i]) != 0:
            print(-1)
            return
    print(day)
    
resolve()
### BUGGY CODE ###

import numpy
N, K = map(int, input().split())
p = numpy.array(list(map(int, input().split())))
max = 0
for i in range(N-K+1):
    temp = numpy.sum(p[i:i+K])
    if max < temp:
        max = temp
        maxno = i

exsum = 0

for i in range(K):
    dice = numpy.arange(1, p[i+maxno]+1)
    numpy.sum(dice)/len(dice)
    exsum += numpy.sum(dice)/len(dice)
print(exsum)

### FIXED CODE ###

import numpy
N, K = map(int, input().split())
p = numpy.array(list(map(int, input().split())))
max = 0
nowsum = 0
for i in range(N-K+1):
    if i == 0:
        nowsum = numpy.sum(p[i:i+K])
    else:
        nowsum = nowsum - p[i-1] + p[i+K-1]
    if max < nowsum:
        max = nowsum
        maxno = i

exsum = 0

for i in range(K):
    temp = p[i+maxno]
    exsum += (0.5*temp*(temp+1))/temp
print(exsum)
### BUGGY CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)
dic = {}
for i in range(n):
  dic[lst[i]] = i

if lst[0] == 1:
  if n > 1:
    if lst[0] == lst[1]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  tf_lst = [True] * n
  count = 0
  if n > 1:
    for i in range(n):
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[i] = False
      if i >= 1:
        if lst[i] == lst[i - 1]:
          tf_lst[i] = False
      for j in range(2, lst[n - 1] // lst[i] + 1):
        if lst[i] * j in lst:
          num = lst[i] * j
          index = dic[num]
          tf_lst[index] = False
  for i in tf_lst:
    if i:
      count += 1
  print(count)


### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        tf_lst[j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)
### BUGGY CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


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

    ans = 0
    for i in range(60):
        one,zero = 0,0
        for j in range(n):
            if ((1 << i) & a[j]) == (1 << i):
                one +=1
            else:
                zero += 1
        ans += (1 << i) * one * zero
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


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

    ans = 0
    for i in range(60):
        one,zero = 0,0
        for j in range(n):
            if ((1 << i) & a[j]) == (1 << i):
                one +=1
            else:
                zero += 1
        ans += (1 << i) * one * zero
        ans %= MOD
    print(ans)


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

N,K=map(int, input().split())
h=list(map(int, input().split()))
 
# dpの最小値を変更する関数
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
      
f_inf = float('inf')
dp = [f_inf]*N
dp[0]=0
#dp[1]=abs(h[1]-h[0])
 
#配るDP
for i in range(N-1):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j]=chmin(abs(h[i]-h[i+j])+dp[i],dp[i+j])
    
print(dp[-1])

### FIXED CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

N,K=map(int, input().split())
h=list(map(int, input().split()))
import numpy as np 
      
f_inf = float('inf')
dp = [f_inf]*N
dp[0]=0
# hの配列を作る。
h = np.array(h)
 
#配るDP
for i in range(1,N):
    # start は負になることはない。
    start = max(0, i-K)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))
    
print(dp[-1])
### BUGGY CODE ###

[X,Y,Z,K] = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
AB = []
for a in A:
    for b in B:
        AB.append(a+b)
AB.sort(reverse=True)
ABC = []
for ab in AB[:K]:
    for c in C:
        ABC.append(ab+c)
ABC.sort(reverse=True)
for i in ABC[:K]:print(i)

### FIXED CODE ###

[XYZK,A,B,C] = [input() for i in range(4)]
[X,Y,Z,K] = [int(i) for i in XYZK.split()]
A = sorted([int(i) for i in A.split()],reverse=True)[:K]
B = sorted([int(i) for i in B.split()],reverse=True)[:K]
C = sorted([int(i) for i in C.split()],reverse=True)[:K]

ABC = []
for i in range(X):
    if (i + 1) > K:
        break
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for l in range(Z):
            if (i + 1) * (j + 1) * (l + 1) > K:
                break
            ABC.append(A[i] + B[j] + C[l])
ABC = sorted(ABC, reverse=True)
print(*ABC[:K])
### BUGGY CODE ###

import itertools
import math

if __name__ == '__main__':
    N, K = map(int, input().split())

    answer = 0
    for c in list(itertools.combinations(range(1, N+1), K)):
        c_list = sorted(list(c))
        min_c_element = min(c_list)
        continue_num = list(range(min_c_element, min_c_element + K))
        if c_list == continue_num:
            answer += 1
    print(answer)


### FIXED CODE ###

if __name__ == '__main__':
    N, K = map(int, input().split())

    answer = N - K + 1
    print(answer)
### BUGGY CODE ###

import sys

def main():
  input = sys.stdin.readline
  S = str(input().strip())
  T = str(input().strip())
  for i in range(len(S)):
    if S[i] == T[i]:
      continue
    else:
      c1, c2 = S[i], T[i]
      S = S.replace(c1, ' ')
      S = S.replace(c2, c1)
      S = S.replace(' ', c2)
  
  if S == T:
    print('Yes')
  else:
    print('No')


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  S = str(input().strip())
  T = str(input().strip())
  
  C1, C2 = [], []
  ans = 'Yes'
  S2T = dict()
  T2S = dict()
  for c1, c2 in zip(S, T):
    if (c1 in S2T) and (c2 in T2S):
      if (S2T[c1] == c2) and (T2S[c2] == c1):
        continue
      else:
        ans = 'No'
        break
    elif (c1 in S2T):
      if S2T[c1] == c2:
        T2S[c2] = c1
        continue
      else:
        ans = 'No'
        break
    elif (c2 in T2S):
      if T2S[c2] == c1:
        S2T[c1] == c2
        continue
      else:
        ans = 'No'
        break
    else:
      S2T[c1] = c2
      T2S[c2] = c1
  print(ans)


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

def main():
    from collections import deque
    S = deque(list(input()))
    Q = int(input())

    for _ in range(Q):
        query = deque(input().split())
        if query[0] == "1":
            S.reverse()
        elif query[1] == "1":
            S.appendleft(query[2])
        elif query[1] == "2" :
            S.append(query[2])

    print("".join(map(str, S)))

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
is_reversed = 1
for _ in range(Q):
    query = list(input().split())
    if query[0] == "1":
        is_reversed *= -1
    
    else:
        if is_reversed == 1:
            if query[1] == "1":
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if query[1] == "2":
                S.appendleft(query[2])
            else:
                S.append(query[2])

S = "".join(S)
print(S[::is_reversed])
### BUGGY CODE ###

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

if abs(M-N) > 1:
    print(0)
    exit()

L = 0
if N == M:
    cnt = 1
    for i in range(1,N+1):
        cnt *= i
    ccnt = cnt
else:
    mi = min([N,M])
    ma = max([N,M])
    cnt = 1
    for i in range(1,mi+1):
        cnt *= i

    ccnt = cnt * ma


nn = N%2
mm = M%2
if (nn == 0 and mm == 0) or (nn == 1 and mm == 1):
    print((cnt * ccnt * 2) % 1000000007)
else:
    print((cnt * ccnt) % 1000000007)


### FIXED CODE ###

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

if abs(M-N) > 1:
    print(0)
    exit()

L = 0
if N == M:
    cnt = 1
    for i in range(1,N+1):
        cnt *= i
        cnt %= 1000000007
    ccnt = cnt
else:
    mi = min([N,M])
    ma = max([N,M])
    cnt = 1
    for i in range(1,mi+1):
        cnt *= i
        cnt %= 1000000007

    ccnt = cnt * ma


nn = N%2
mm = M%2
if (nn == 0 and mm == 0) or (nn == 1 and mm == 1):
    print((cnt * ccnt * 2) % 1000000007)
else:
    print((cnt * ccnt) % 1000000007)
### BUGGY CODE ###

N,x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
count = 0

for i in range(N-1):
    while a[i] + a[i+1] > x:
        a[i+1] -= 1
        count += 1

print(count)


### FIXED CODE ###

N,x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
count = 0

while a[0] > x:
    count += a[0] - x
    a[0] = x

for i in range(N-1):
    if a[i] + a[i+1] > x:
        count += a[i+1] - (x - a[i])
        a[i+1] = x - a[i]

print(count)
### BUGGY CODE ###

n,m = map(int,input().split())
a_ls = list(map(int, input().split()))
a_ls.sort()
def isOK(index, key, l):
    if l[index] >= key:
        return True
    else:
        return False
def meguru_search(l, key):
    '''
    key以上の値を持つ最小のインデックスを返す
    '''
    left = -1
    right = len(l)

    while (right - left) > 1:
        mid = left + (right - left) // 2
        # 直感的に記憶　
            # 「含まれている」んだったら「含むを許容（等号付き）する右側」はmidまで動かして問題ない
                # 新しいrightの位置がkeyの位置だとしても、「含む」は許容されてる
            # 「含まれていない」んだったら「含まない(<)左の壁」をそこまで動かしてもkeyを通り過ぎることはない
        if isOK(mid, key, l):
            right = mid
        else:
            left = mid
    
    # whileを抜ける時、rightとleftは一個差で、かつkeyがrightの位置にある
    return right
for i in range(m):
    b,c = map(int,input().split())
    ind = meguru_search(a_ls, c)
    # ind==bより小さい数が書かれたカードの数
    if ind >= b:
        a_ls[:b] = [c for _ in range(b)]
    else:
        a_ls[:ind] = [c for _ in range(ind)]
    a_ls.sort()
print(sum(a_ls))



### FIXED CODE ###

from collections import Counter
n,m = map(int,input().split())
a_ls = list(map(int, input().split()))
counter = Counter(a_ls)
for i in range(m):
    b,c = map(int,input().split())
    counter[c] += b

cards = sorted(counter.items(), key = lambda x:x[0], reverse=True)
rest = n
Sum = 0
for num, count in cards:
    if count < rest:
        Sum += num * count
        rest -= count
    else:
        Sum += rest * num
        break
print(Sum)
### BUGGY CODE ###

from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

lo, hi = 0, max(a*f for (a, f) in zip(A,F))
while lo < hi:
    mid = (lo + hi)//2
    rsd = K
    possible = True
    for a, f in zip(A,F):
        rsd -= ceil(max(a*f-mid, 0)/f)
        if rsd < 0:
            possible = False
            break
    if possible:
        hi = mid
    else:
        lo = mid+1

print(lo)


### FIXED CODE ###

from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

lo, hi = 0, max(a*f for (a, f) in zip(A,F))
while lo < hi:
    mid = (lo + hi)//2
    rsd = K
    possible = True
    for a, f in zip(A,F):
        rsd -= ceil(max(a*f-mid, 0)/f)
        if rsd < 0:
            possible = False
            break
    if possible:
        hi = mid
    else:
        lo = mid+1

print(lo)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline

    _, _, m = input().split()
    m = int(m)
    alist = input().split()
    blist = input().split()

    waribiki = [input().split() for _ in range(m)]
    
    res = []
    for a in alist:
      for b in blist:
        res.append(int(a)+int(b))
    for i in range(m):
        res.append(int(alist[int(waribiki[i][0])-1]) + int(blist[int(waribiki[i][1])-1]) - int(waribiki[i][2]))
      
    print(min(res))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

    a, b, m = input().split()
    a, b, m = int(a), int(b), int(m)
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))

    waribiki = [input().split() for _ in range(m)]
    
    res = [200000] * (m + 1)
    count = 0

    for i in range(m):
        res[count] = alist[int(waribiki[i][0])-1] + blist[int(waribiki[i][1])-1] - int(waribiki[i][2])
        count += 1

    res[count] = min(alist) + min(blist)
      
    print(min(res))


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

import sys,random
input = sys.stdin.readline


def main():
    n = int(input())
    
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    for k in range(n):
        hyp = b[0]^a[k]
        judge = True
        for _ in [0]*30:
            w = random.randrange(n)
            if b[w] != a[(w+k)%n]^hyp:
                judge = False
                break
        if judge:
            print(k,hyp)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg


n = int(input())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))


BAA = []
for i in range(n-1):
    BAA.append(b[i]^b[i+1])
BAA.append(b[0]^b[-1])

BAA.append(-1)

for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])
for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])

z = Z_algorithm(BAA)

for k in range(n):
    if z[n+k+1] >= n:
        print(k,b[0]^a[k])