CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline
from operator import itemgetter

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

Max = [[(0, A[0])]]
ans = 0
for bit in range(1, (1<<N)):
    dic = {}
    for i in range(N):
        if bit&(1<<i) != 0:
            for ind, val in Max[bit-(1<<i)]:
                dic[ind] = val
    com = [(bit, A[bit])]
    for ind, val in list(dic.items()):
        com.append((ind, val))
    com.sort(reverse=True, key=itemgetter(1))
    Max.append(com[:2])
    tmp = com[0][1] + com[1][1]
    if tmp > ans:
        ans = tmp
    print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

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

Max = [[(0, A[0])]]
ans = 0
for bit in range(1, (1<<N)):
    dic = {bit: A[bit]}
    for i in range(N):
        if bit&(1<<i) != 0:
            for ind, val in Max[bit-(1<<i)]:
                dic[ind] = val
    com = []
    for ind, val in list(dic.items()):
        if len(com) < 2:
            com.append((ind, val))
        else:
            if com[0][1] < com[1][1]:
                if com[0][1] < val:
                    com[0] = (ind, val)
                elif com[1][1] < val:
                    com[1] = (ind, val)
            else:
                if com[1][1] < val:
                    com[1] = (ind, val)
                elif com[0][1] < val:
                    com[0] = (ind, val)               
    Max.append(com)
    tmp = com[0][1] + com[1][1]
    if tmp > ans:
        ans = tmp
    print(ans)
# Original solution
import sys
input = sys.stdin.readline
from itertools import accumulate

def merge(x, y):
  D = sorted([dp[x][0], dp[x][1], dp[y][0], dp[y][1]], reverse=True)
  return (D[0], D[1])
  
n = int(input())
A = tuple(map(int, input().split()))
dp = [(a, 0) for a in A]
for j in range(n):
  for i in range(1<<n):
    if i & (1<<j):
      dp[i] = merge(i, i & ~(1<<j))
L = tuple(accumulate((sum(d) for d in dp), max))
print(*L[1:], sep="\n")


# Optimized solution
import sys
input = sys.stdin.readline
from itertools import accumulate

def merge(x, y):
  a, b = dp[x]
  c, d = dp[y]
  if a >= c:
    return (a, max(c, b))
  return (c, max(a, d))
  
n = int(input())
A = tuple(map(int, input().split()))
dp = [(a, 0) for a in A]
for j in range(n):
  for i in range(1<<n):
    if i & (1<<j):
      dp[i] = merge(i, i & ~(1<<j))
L = tuple(accumulate((sum(d) for d in dp), max))
print(*L[1:], sep="\n")
# Original solution
n = int(input())
a = list(map(int, input().split()))
b = [[i, 1<<n] for i in range(len(a))]
a.append(-float("inf"))

def update(a1, a2):
    a1.extend(a2)
    return sorted(set(a1), key=lambda x: -a[x])[:2]

for j in range(n):
    for i in range(1<<n):
        if i & (1<<j):
            b[i] = update(b[i], b[i & ~(1<<j)])
ans = []
tmp = 0
for i in range(1, 1<<n):
    tmp = max(tmp, a[b[i][0]]+a[b[i][1]])
    ans.append(tmp)
print(*ans, sep="\n")


# Optimized solution
n = int(input())
a = list(map(int, input().split()))
b = [[i] for i in a]

for j in range(n):
    for i in range(1<<n):
        if i & (1<<j):
            b[i] = sorted(b[i]+b[i^1<<j], reverse=True)[:2]
ans = []
tmp = 0
for i in range(1, 1<<n):
    tmp = max(tmp, sum(b[i]))
    ans.append(tmp)
print(*ans, sep="\n")
# Original solution
#import numpy as np

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

#dp[S] = A[S], -inf で初期化　Sの部分集合TのうちA[T]が(最大のもの, 次に大きいもの)　を入れていく

dp = [[A[S], -float('inf') ] for S in range(1 << N)]
for i in range(N):
    for T in range( 1 << N):
        if (T >> i) & 1 == 1: # Tがiを含むとき
            merge = dp[T] + dp[T ^ (1 << i)]
            merge.sort(reverse = True)
            dp[T] =merge[:2]
ans = -float('inf')
for S in range(1, 1 << N , 1):
    ans = max(ans, sum(dp[S]))
    print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
 
#dp[S] = A[S], -inf で初期化　Sの部分集合TのうちA[T]が(最大のもの, 次に大きいもの)　を入れていく
 
dp = [[A[S], -float('inf') ] for S in range(1 << N)]
for i in range(N):
    for T in range( 1 << N):
        if (T >> i) & 1 == 1: # Tがiを含むとき
            merge = dp[T] + dp[T ^ (1 << i)]
            merge.sort(reverse = True)
            dp[T] =merge[:2]
ans = -float('inf')
for S in range(1, 1 << N , 1):
    ans = max(ans, sum(dp[S]))
    print(ans)
# Original solution
N = int(eval(input()))
A = [[(0, 0)] * (1<<N) for _ in range(N+1)]
A[0] = [(int(a), 0) for a in input().split()]
combine = lambda a, b: a if a[1] >= b[0] else b if b[1] >= a[0] else (a[0], b[0]) if a[0] > b[0] else (b[0], a[0])

for i in range(1, N+1):
    ii = 1 << i - 1
    for j in range(1<<N):
        if j & ii:
            A[i][j] = combine(A[i-1][j], A[i-1][j^ii])
        else:
            A[i][j] = A[i-1][j]

ANS = [0] * (1<<N)
for i in range(1, 1<<N):
    ANS[i] = max(ANS[i-1], sum(A[-1][i]))

print(("\n".join(map(str, ANS[1:]))))

# Optimized solution
N = int(eval(input()))
A = [(int(a), 0) for a in input().split()]
combine = lambda a, b: a if a[1] >= b[0] else b if b[1] >= a[0] else (a[0], b[0]) if a[0] > b[0] else (b[0], a[0])

for i in range(N):
    ii = 1 << i
    for j in range(1<<N)[::-1]:
        if j & ii:
            A[j] = combine(A[j], A[j^ii])

ANS = [0] * (1<<N)
for i in range(1, 1<<N):
    ANS[i] = max(ANS[i-1], sum(A[i]))

print(("\n".join(map(str, ANS[1:]))))
# Original solution
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

def func():
    N = int(eval(input()))

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** N)]

    for i in range(1, 2 ** N):
        if (A[i], i) > P[i][0]:
            P[i][1] = P[i][0]
            P[i][0] = (A[i], i)
        elif (A[i], i) > P[i][1]:
            P[i][1] = (A[i], i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                index = i + (1 << j)
                for k in range(2):
                    if P[i][k] > P[index][0]:
                        P[index][1] = P[index][0]
                        P[index][0] = P[i][k]
                    elif P[i][k] > P[index][1] and P[i][k] != P[index][0]:
                        P[index][1] = P[i][k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()

# Optimized solution
#!/usr/bin/env python

#from collections import deque
#import itertools as it
#import sys
#import math

def func():
    N = int(eval(input()))

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** N)]

    for i in range(1, 2 ** N):
        if (A[i], i) > P[i][0]:
            P[i][1] = P[i][0]
            P[i][0] = (A[i], i)
        elif (A[i], i) > P[i][1]:
            P[i][1] = (A[i], i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                index = i + (1 << j)
                for k in range(2):
                    if P[i][k] > P[index][0]:
                        P[index][1] = P[index][0]
                        P[index][0] = P[i][k]
                    elif P[i][k] > P[index][1] and P[i][k] != P[index][0]:
                        P[index][1] = P[i][k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()
# Original solution
import sys
from pprint import pprint

def solve(s):
    w = ["Sunny", "Cloudy", "Rainy"]
    print((w[(w.index(s) + 1) % 3]))

if __name__ == '__main__':
    s = sys.stdin.readline().strip()
    solve(s)

# Optimized solution
import sys

S = sys.stdin.readline().strip()
weathers = ["Sunny", "Cloudy", "Rainy"]
print((weathers[(weathers.index(S) + 1) % 3]))
# Original solution
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


d = {'Sunny':'Cloudy','Cloudy':'Rainy','Rainy':'Sunny'}
print((d[S()]))


# Optimized solution
import sys
def S(): return sys.stdin.readline().rstrip()


d = {'Sunny':'Cloudy','Cloudy':'Rainy','Rainy':'Sunny'}
print((d[S()]))
# Original solution
import sys
import itertools
wether = input()
base = ['Sunny','Cloudy','Rainy']

if wether not in base: sys.exit()

print(base[base.index(wether)+1]) if wether != base[-1] else print(base[0])


# Optimized solution
import sys
wether = input()
base = ['Sunny','Cloudy','Rainy']

if wether not in base: sys.exit()

print(base[base.index(wether)+1]) if wether != base[-1] else print(base[0])
# Original solution
S = input().strip()
if S=="Sunny":
    print("Cloudy")
elif S=="Cloudy":
    print("Rainy")
elif S=="Rainy":
    print("Sunny")

# Optimized solution
S = input().strip()
if S=="Sunny":
    print("Cloudy")
elif S=="Cloudy":
    print("Rainy")
else:
    print("Sunny")
# Original solution
def slove():
    import sys
    input = sys.stdin.readline
    d = {"Sunny": "Cloudy", "Cloudy": "Rainy", "Rainy": "Sunny"}
    s = str(input().rstrip('\n'))
    print((d[s]))


if __name__ == '__main__':
    slove()


# Optimized solution
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    elif s == "Rainy":
        print("Sunny")


if __name__ == '__main__':
    solve()
# Original solution
# 日立コン
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

A, B, M = list(map(int, readline().split()))

Alist = list(map(int, readline().split()))
Blist = list(map(int, readline().split()))

answer = 10 ** 7
for a in Alist:
    for b in Blist:
        tmp = a + b
        if tmp < answer:
            answer = tmp

for _ in range(0, M):
    x, y, c = list(map(int, readline().split()))
    tmp = Alist[x-1] + Blist[y-1] - c
    if tmp < answer:
        answer = tmp
if answer > 0:
    print(answer)
else:
    print((0))

# Optimized solution
# 日立コン
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

A, B, M = list(map(int, readline().split()))

Alist = list(map(int, readline().split()))
Blist = list(map(int, readline().split()))

min_a = min(Alist)
min_b = min(Blist)
answer = min_a + min_b

for _ in range(0, M):
    x, y, c = list(map(int, readline().split()))
    tmp = Alist[x-1] + Blist[y-1] - c
    answer = min(answer, tmp)

if answer > 0:
    print(answer)
else:
    print((0))
# Original solution
R = lambda: tuple(map(int, input().split()))
A, B, M = R()
a, b = R(), R()
d = (R() for _ in range(M))
print((min([min(a) + min(b)] + [a[x - 1] + b[y - 1] - c for x, y, c in d])))


# Optimized solution
R = lambda: tuple(map(int, input().split()))
A, B, M = R()
a, b = R(), R()
d = (R() for _ in range(M))
print((min(min(a) + min(b), *(a[x - 1] + b[y - 1] - c for x, y, c in d))))
# Original solution
A, B, M = list(map(int, input().split()))
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
coupons = []
for _ in range(M):
    coupons.append(list(map(int, input().split())))

target = list(coupon[:2] for coupon in coupons)
best_sum = 10000


def my_index(l, x, default=-1):
    if x in l:
        return l.index(x)
    else:
        return default

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

for a in range(A):
    for b in range(B):
        index = my_index_multi(target, [a+1, b+1])
        if len(index) > 0:
            for i in index:
                sum_value = As[a]+Bs[b]-coupons[i][2]
                if best_sum > sum_value:
                    best_sum = sum_value
        else:
            sum_value = As[a]+Bs[b]
            if best_sum > sum_value:
                best_sum = sum_value
        
print(best_sum)

# Optimized solution
A, B, M = list(map(int, input().split()))
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
coupons = []
for _ in range(M):
    coupons.append(list(map(int, input().split())))

a_min = min(As)
b_min = min(Bs)

best_sum = a_min+b_min
coupons_sums = []
for l in coupons:
    coupons_sums.append(As[l[0]-1] + Bs[l[1]-1] - l[2])
    
for coupons_sum in coupons_sums:
    if best_sum > coupons_sum:
        best_sum = coupons_sum

print(best_sum)
# Original solution
A, B, M = [int(x) for x in input().split()]
A_price_list = [int(x) for x in input().split()]
B_price_list = [int(x) for x in input().split()]

discount_list = [[0 for j in range(B)] for i in range(A)]

for i in range(M):
    x, y, c = ([int(x) for x in input().split()])
    discount_list[x-1][y-1] = max(discount_list[x-1][y-1], c)


amount = 9999999999999999999999999
for i in range(A):
    for j in range(B):
        tmp_amount = A_price_list[i] + B_price_list[j] - discount_list[i][j]
        amount = min(amount, tmp_amount)

print(amount)

# Optimized solution
A, B, M = [int(x) for x in input().split()]
A_price_list = [int(x) for x in input().split()]
B_price_list = [int(x) for x in input().split()]

discount_list = []

for i in range(M):
    x, y, c = [int(x) for x in input().split()]
    discount_list.append([x-1, y-1, c])


amount = min(A_price_list) + min(B_price_list)

for x, y, c in discount_list:
    tmp_price = A_price_list[x] + B_price_list[y] - c
    amount = min(tmp_price, amount)

print(amount)
# Original solution
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mini = 2*10**5
for i in range(M):
  num = list(map(int, input().split()))
  tmp = a[num[0]-1] + b[num[1]-1] - num[2]
  if tmp < mini:
    mini = tmp
for i in range(A):
  if a[i] > mini:
    continue
  for j in range(B):
    if a[i]+b[j] < mini:
      mini = a[i]+b[j]
      
print(mini)

# Optimized solution
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mini = 2*10**5
for i in range(M):
  num = list(map(int, input().split()))
  tmp = a[num[0]-1] + b[num[1]-1] - num[2]
  if tmp < mini:
    mini = tmp
mini = min(mini, min(a)+min(b))
      
print(mini)
# Original solution
n_a,n_b,M=list(map(int,input().split()))
A=list(map(int,input().split()))
B=list(map(int,input().split()))
price=[]
for i in range(M):
    X=list(map(int,input().split()))
    price.append(A[X[0]-1]+B[X[1]-1]-X[2])
for i in range(n_a):
    for j in range(n_b):
        price.append(A[i]+B[j])
print((min(price)))

# Optimized solution
n_a,n_b,M=list(map(int,input().split()))
A=list(map(int,input().split()))
B=list(map(int,input().split()))
price=[]
for i in range(M):
    X=list(map(int,input().split()))
    price.append(A[X[0]-1]+B[X[1]-1]-X[2])
price.append(min(A)+min(B))
print((min(price)))
# Original solution
#入力処理
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
waribiki=[[0]*B]*A
for i in range(M):
    x_input, y_input, c_input = list(map(int, input().split()))
    if waribiki[x_input-1][y_input-1]<c_input:
        waribiki[x_input-1][y_input-1]=c_input

#処理
inexpensive=200000
for i in range(A):
    for j in range(B):
        if (int(a[i])+int(b[j]))-waribiki[i][j] < inexpensive:
            inexpensive = (int(a[i])+int(b[j]))-waribiki[i][j]

print(inexpensive) 

# Optimized solution
#入力処理
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
kingaku=[]
for i in range(M):
    x_input, y_input, c_input = list(map(int, input().split()))
    kingaku.append(a[x_input-1]+b[y_input-1]-c_input)
kingaku.append(min(a)+min(b))

print((min(kingaku)))
# Original solution
# coding: utf-8
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

z = [list(map(int, input().split())) for _ in range(M)]

num1 = [a[i] + b[j] for i in range(A) for j in range(B)]
# print("num1:", num1)        

for i in range(M):
    x, y, c = z[i]
    num = a[x - 1] + b[y - 1] - c
    num1.append(num)
# print(num1)
print((min(num1)))

# Optimized solution
# coding: utf-8
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

z = [list(map(int, input().split())) for _ in range(M)]

num1 = {a[i] + b[j] for i in range(A) for j in range(B)}
# print("num1:", num1)        
num1 = min(num1)
# print("num1:", num1)
for i in range(M):
    x, y, c = z[i]
    num = a[x - 1] + b[y - 1] - c
    if num < num1:
        num1 = num
print(num1)
# Original solution
# coding: utf-8
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

z = [list(map(int, input().split())) for _ in range(M)]

num1 = {a[i] + b[j] for i in range(A) for j in range(B)}
# print("num1:", num1)        
num1 = min(num1)
# print("num1:", num1)
for i in range(M):
    x, y, c = z[i]
    num = a[x - 1] + b[y - 1] - c
    if num < num1:
        num1 = num
print(num1)

# Optimized solution
# coding: utf-8
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a1 = sorted(a)
b1 = sorted(b)
z = [list(map(int, input().split())) for _ in range(M)]

num1 = a1[0] + b1[0]
# print("num1:", num1)
for i in range(M):
    x, y, c = z[i]
    num = a[x - 1] + b[y - 1] - c
    if num < num1:
        num1 = num
print(num1)
# Original solution
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
X = [list(map(int, input().split())) for i in range(M)]

ans = [min(a) + min(b)]
for x in X:
    a_idx, b_index, c = x
    ans.append(a[a_idx - 1] + b[b_index - 1] - c)

print((min(ans)))

# Optimized solution
a,b,m = list(map(int,input().split()))
a_li = list(map(int,input().split()))
b_li = list(map(int,input().split()))
cost = min(a_li) + min(b_li)
for i in range(m):
  x,y,c = list(map(int,input().split()))
  price = a_li[x-1] + b_li[y-1] - c
  if price < cost:
    cost = price
print(cost)
# Original solution
a, b, m = list(map(int, input().split()))

aa = list(map(int, input().split()))
bb = list(map(int, input().split()))

mm = list()
for ii in range(0,m):
    mm.append(list(map(int, input().split())))

prices = list()

for ml in mm:
    prices.append(aa[ml[0]-1] + bb[ml[1]-1] - ml[2])

for al in aa:
    for bl in bb:
        prices.append(al + bl)

print((min(prices)))


# Optimized solution
a, b, m = list(map(int, input().split()))

aa = list(map(int, input().split()))
bb = list(map(int, input().split()))

mm = list()
for ii in range(0,m):
    mm.append(list(map(int, input().split())))

prices = list()

prices.append(int(min(aa)) + int(min(bb)))

for ml in mm:
    prices.append(aa[ml[0]-1] + bb[ml[1]-1] - ml[2])

print((min(prices)))
# Original solution
f=lambda:list(map(int,input().split()))
_,_,n=f()
a,b=list(f()),list(f())
m=min(a)+min(b)
for _ in range(n): x,y,c=f(); m=min(m,a[x-1]+b[y-1]-c)
print(m)

# Optimized solution
import sys
f=lambda:list(map(int,sys.stdin.readline().split()))
_,_,n=f()
a,b=list(f()),list(f())
m=min(a)+min(b)
for _ in range(n): x,y,c=f(); m=min(m,a[x-1]+b[y-1]-c)
print(m)
# Original solution
a,b,m=list(map(int, input().split()))
A=list(map(int, input().split()))
B=list(map(int, input().split()))
tickets=list()
for i in range(m):
    tickets.append(list(map(int,input().split())))

price_min=float("INF")
for ticket in tickets:
    price = A[ticket[0]-1] + B[ticket[1]-1] - ticket[2]
    price_min = price if price_min>price else price_min

# 割引券を使わない場合
for _a in A:
    for _b in B:
        price=_a + _b
        price_min=price if price_min > price else price_min
        if price <_a:
            break
print(price_min)

# Optimized solution
a,b,m=list(map(int, input().split()))
A=list(map(int, input().split()))
B=list(map(int, input().split()))
tickets=list()
for i in range(m):
    tickets.append(list(map(int,input().split())))

price_min=float("INF")
for ticket in tickets:
    price = A[ticket[0]-1] + B[ticket[1]-1] - ticket[2]
    price_min = price if price_min>price else price_min

# 割引券を使わない場合
no_ticket=min(A)+min(B)
if price_min > no_ticket: price_min=no_ticket
print(price_min)
# Original solution
a,b,m = list(map(int,input().split()))
alist = list(map(int,input().split()))
blist = list(map(int,input().split()))
mlist = [list(map(int,input().split())) for s in range(m)]
ans = []
for m in mlist:
	tmp = alist[m[0]-1] + blist[m[1]-1] -m[2]
	ans.append(tmp)
for a in alist:
	for b in blist:
		ans.append(a + b)
print((min(ans)))

# Optimized solution
a,b,m = list(map(int,input().split()))
alist = list(map(int,input().split()))
blist = list(map(int,input().split()))
mlist = [list(map(int,input().split())) for s in range(m)]
ans = []
for m in mlist:
	tmp = alist[m[0]-1] + blist[m[1]-1] -m[2]
	ans.append(tmp)
x = min(alist) + min(blist)
ans.append(x)
print((min(ans)))
# Original solution
import sys
A, B, M = list(map(int, input().split()))
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
# discounts = list(list(map(int, input().split())) for _ in )

discounts = dict()
for discount in sys.stdin:
    x, y, c = discount.split()
    c = int(c)
    if x in discounts:
        if y in discounts[x]:
            if discounts[x][y] < c:
                discounts[x][y] = c
        else:
            discounts[x][y] = c
    else:
        discounts[x] = {y: c}

min = -1
for i in range(len(a_list)):
    b_line_prices = []
    for j in range(len(b_list)):
        price = a_list[i] + b_list[j]
        x = str(i + 1)
        y = str(j + 1)
        if x in discounts:
            if y in discounts[x]:
                price -= discounts[x][y]
        if min == -1 or price < min:
            min = price
print(min)

# Optimized solution
import sys
A, B, M = list(map(int, input().split()))
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

ans = min(a_list) + min(b_list)
for discount in sys.stdin:
    x, y, c = list(map(int, discount.split()))
    ans = min(ans, a_list[x - 1] + b_list[y - 1] - c)
print(ans)
# Original solution
A, B, M = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
xyc = [[int(_) for _ in input().split()] for i in range(M)]

rets = []
for i in a:
    for j in b:
        rets += [i + j]
for x, y, c in xyc:
    rets += [a[x-1] + b[y-1] - c]
print((min(rets)))

# Optimized solution
A, B, M = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
xyc = [[int(_) for _ in input().split()] for i in range(M)]

rets = [min(a) + min(b)]

for x, y, c in xyc:
    rets += [a[x-1] + b[y-1] - c]
print((min(rets)))
# Original solution
A, B, M = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
discountDic = {}
for i in range(M):
    x, y, c = list(map(int, input().split(' ')))
    key = (x-1)*B+(y-1)
    if key not in discountDic or discountDic[key] < c:
        discountDic[key] = c
priceList = []
for i in range(A):
    for j in range(B):
        price = a[i] + b[j]
        if i*B+j in discountDic:
            price -= discountDic[i*B+j]
        priceList.append(price)
print((min(priceList)))

# Optimized solution
A, B, M = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
discountDic = {}
for i in range(M):
    x, y, c = list(map(int, input().split(' ')))
    key = (x-1)*B+(y-1)
    if key not in discountDic or discountDic[key] > a[x-1] + b[y-1] - c:
        discountDic[key] = a[x-1] + b[y-1] - c
discount_min_price = min(discountDic.values())
all_low_price = min(a) + min(b)
if discount_min_price < all_low_price:
    print(discount_min_price)
else:
    print(all_low_price)