Problem:


Score : 200 points

Problem Statement

You are visiting a large electronics store to buy a refrigerator and a microwave.

The store sells A kinds of refrigerators and B kinds of microwaves. The i-th refrigerator ( 1 \le i \le A ) is sold at a_i yen (the currency of Japan), and the j-th microwave ( 1 \le j \le B ) is sold at b_j yen.

You have M discount tickets. With the i-th ticket ( 1 \le i \le M ), you can get a discount of c_i yen from the total price when buying the x_i-th refrigerator and the y_i-th microwave together. Only one ticket can be used at a time.

You are planning to buy one refrigerator and one microwave. Find the minimum amount of money required.

Constraints

All values in input are integers.

 1 \le A \le 10^5 

 1 \le B \le 10^5 

 1 \le M \le 10^5 

 1 \le a_i , b_i , c_i \le 10^5 

 1 \le x_i \le A 

 1 \le y_i \le B 

 c_i \le a_{x_i} + b_{y_i} 

Input

Input is given from Standard Input in the following format:

A B M
a_1 a_2 ... a_A
b_1 b_2 ... b_B
x_1 y_1 c_1
\vdots
x_M y_M c_M

Output

Print the answer.

Sample Input 1

2 3 1
3 3
3 3 3
1 2 1

Sample Output 1

5

With the ticket, you can get the 1-st refrigerator and the 2-nd microwave for 3+3-1=5 yen.

Sample Input 2

1 1 2
10
10
1 1 5
1 1 10

Sample Output 2

10

Note that you cannot use more than one ticket at a time.

Sample Input 3

2 2 1
3 5
3 5
2 2 2

Sample Output 3

6

You can get the 1-st refrigerator and the 1-st microwave for 6 yen, which is the minimum amount to pay in this case.
Note that using a ticket is optional.



Sample input:
2 3 1
3 3
3 3 3
1 2 1


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
def main():
    a, b, m = map(int, input().split())
    priceOfMicrowaves = list(map(int, input().split()))
    priceOfRefrigerators = list(map(int, input().split()))
    priceTable = [list(map(int,input().split())) for i in range(m)]
    cheepest = priceOfMicrowaves[0] + priceOfRefrigerators[0]
    for price in priceTable:
        if priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2] < cheepest:
            cheepest = priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2]
    for p in priceOfMicrowaves:
        if p >= cheepest:
            continue
        for q in priceOfRefrigerators:
            if q >= cheepest:
                continue
            if p + q < cheepest:
                cheepest = p + q
    print(cheepest)
    
main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
A, B, M = 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)

Submission status: Time Limit Exceeded

Solution code:
ABM = list(map(int, input().split()))
price_A = list(map(int, input().split()))
price_B = list(map(int, input().split()))

waribiki = []
for i in range(ABM[2]):
    waribiki.append(list(map(int, input().split())))

result = []
for i in waribiki:
    for i_A in price_A:
        for i_B in price_B:
            result.append(i_A + i_B)
    result.append(price_A[i[0] - 1] + price_B[i[1] - 1] - i[2])

print(min(result))

Submission status: Time Limit Exceeded

Solution code:
a, b, m = map(int, input().split())
ref = list(map(int, input().split()))
micro = list(map(int, input().split()))
tk = [list(map(int, input().split())) for i in range(m)]

mini = 10 ** 6
for i in range(a):
    for j in range(b):
        s = ref[i] + micro[j]
        if s < mini:
            mini = s

amount = 10 ** 6
for i in tk:
    if ref[i[0]-1] + micro[i[1]-1] - i[2] < amount:
        amount = ref[i[0]-1] + micro[i[1]-1] - i[2]

print(min(mini, amount))

Submission status: Time Limit Exceeded

Solution code:
def main():
    a, b, m = map(int, input().split())
    priceOfMicrowaves = list(map(int, input().split()))
    priceOfRefrigerators = list(map(int, input().split()))
    priceTable = [list(map(int,input().split())) for i in range(m)]
    cheepest = priceOfMicrowaves[0] + priceOfRefrigerators[0]
    for price in priceTable:
        if priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2] < cheepest:
            cheepest = priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2]
    for p in priceOfMicrowaves:
        for q in priceOfRefrigerators:
            if p + q < cheepest:
                cheepest = p + q
    print(cheepest)
    
main()

Submission status: Time Limit Exceeded

Solution code:
A , B , M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = []
for i in range(A):
    for j in range(B):
        x = a[i] + b[j]
        ans.append(x)
for i in range(M):
    q = list(map(int, input().split()))
    x = a[q[0]-1] + b[q[1]-1] - q[2]
    ans.append(x)
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

    waribiki = [input().split() for _ in range(m)]
    
    res = [200000] * 200001
    count = 0
    for i in range(a):
      for j in range(b):
        try:
            res[count] = int(alist[i]) + int(blist[j])
        except Exception:
            pass
        count += 1

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = list(map(int, input().split(" ")))

a = s[0]
b = s[1]
m = s[2]

a_l = list(map(int, input().split(" ")))
b_l = list(map(int, input().split(" ")))

ans = a_l[0] + b_l[0]

for i in range(m):
    x = list(map(int, input().split(" ")))
    if ans > (a_l[x[0] - 1] + b_l[x[1] -1] - x[2]):
        ans = a_l[x[0] -1] + b_l[x[1] -1] - x[2]
        
while len(a_l) > 0:
    a_ = a_l.pop(0)
    for v in b_l:
        if ans > (a_ + v):
            ans = a_ + v

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
A, B, M = 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))

Submission status: Time Limit Exceeded

Solution code:
def main():
    a, b, m = map(int, input().split())
    priceOfMicrowaves = list(map(int, input().split()))
    priceOfRefrigerators = list(map(int, input().split()))
    priceTable = [list(map(int,input().split())) for i in range(m)]
    cheepest = priceOfMicrowaves[0] + priceOfRefrigerators[0]
    for p in priceOfMicrowaves:
        for q in priceOfRefrigerators:
            if p + q < cheepest:
                cheepest = p + q
    for price in priceTable:
        if priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2] < cheepest:
            cheepest = priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2]
    print(cheepest)
    
main()

Submission status: Time Limit Exceeded

Solution code:
def ABcosts(A, B):
    mincos = 100000
    for i in A:
        for j in B:
            if mincos > i + j:
                mincos = i + j
    return mincos

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

refredge = list(map(int, input().split()))
microwave = list(map(int, input().split()))

discounts = []
costs = []
for i in range(M):
    dis = list(map(int, input().split()))
    cos = (refredge[dis[0]-1] + microwave[dis[1]-1] - dis[2])
    costs.append(cos)
    discounts.append(dis)
abcost = ABcosts(refredge, microwave)
print(min(min(costs), abcost))

Submission status: Time Limit Exceeded

Solution code:
A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
k = []
for i in range(M):
   _x,_y,_c = map(int,input().split()) 
   k.append([_x,_y,_c])
c = 1e6
for x in a:
  for y in b:
    if x+y<c:
      c=x+y
for z in k:
  if a[z[0]-1]+b[z[1]-1]-z[2]<c:
    c=a[z[0]-1]+b[z[1]-1]-z[2]
print(c)

Submission status: Time Limit Exceeded

Solution code:
a, b, m = list(map(int, input().split()))
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
sum_list = []
list1 = []

for i in a_list:
    for j in b_list:
        list1.append(i + j)

for i in range(m):
    x, y, c = list(map(int, input().split()))
    sum = a_list[x - 1] + b_list[y - 1] - c
    sum_list.append(sum)

# print(list1)
# print(sum_list)
print(min(min(sum_list), min(list1)))

Submission status: Time Limit Exceeded

Solution code:
A,B,M=map(int,input().split())
A_list=list(map(int, input().split()))
B_list=list(map(int, input().split()))
M_list=list(list(map(int, input().split())) for i in range(M))
res1=A_list[M_list[0][0]-1]+B_list[M_list[0][1]-1]-M_list[0][2]
for m in range(1,M):
    res1=min(res1,A_list[M_list[m][0]-1]+B_list[M_list[m][1]-1]-M_list[m][2])

res2 = res1
for a in range(A):
    for b in range(B):
        res2 = min(res2,A_list[a]+B_list[b])
print(res2)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    X = np.argsort(A)
    Y = np.argsort(B)

    cmax = 0
    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))
        cmax = max(cmax, int(c))
    ret = A[X[0]]+B[Y[0]]

    for x in X:
        for y in Y:
            if ret < A[x]+B[y]-cmax:
                break
            ret = min(ret, A[x]+B[y]-XYC.get((x, y), 0))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
import sys
A, B, M = 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)

Submission status: Time Limit Exceeded

Solution code:
A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
p = [i+j for i in a for j in b]
for _ in range(M):
    x,y,c = map(int,input().split())
    p.append(a[x-1]+b[y-1]-c)

print(min(p))

Submission status: Time Limit Exceeded

Solution code:
import itertools
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# 2次元配列
grid = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    grid.append(array)
    
sum_fee = []
comb_pro = list(itertools.product(a, b))
for com in comb_pro:
    sum_fee.append(sum(com))

for l, m , n in grid:
    sum_fee.append(a[l-1] + b[m-1] - n)
    
print(min(sum_fee))

Submission status: Time Limit Exceeded

Solution code:
abm=(input().split(" "))
al1=(input().split(" "))
bl1=(input().split(" "))
minp=int(al1[0])+int(bl1[0])

for ai in al1:
    ai=int(ai)
    for bi in bl1:
        bi=int(bi)
        ci=ai+bi
        if minp>ci:
            minp=ci
for n in range(0,int(abm[2])):
    a,b,c = map(int,input().split())
    ci=int(al1[a-1])+int(bl1[b-1])-int(c)
    if minp>ci:
        minp=ci

print(minp)

Submission status: Time Limit Exceeded

Solution code:

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

rei=list(map(int, input().split())) 
den=list(map(int, input().split())) 
cou = [0] * m
ans = []
for i in range(m):
	cou[i]=list(map(int, input().split()))
	ans.append(rei[cou[i][0]-1]+den[cou[i][1]-1]-cou[i][2])
	
for i in range(len(den)):
	for j in range(len(rei)):
		ans.append(rei[j]+den[i])

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
a, b, m = map(int, input().split())
ref = list(map(int, input().split()))
micro = list(map(int, input().split()))
tk = [list(map(int, input().split())) for i in range(m)]

mini = 10 ** 6
for i in range(a):
    for j in range(b):
        if ref[i] + micro[j] < mini:
            mini = ref[i] + micro[j]

amount = 10 ** 6
for i in tk:
    if ref[i[0]-1] + micro[i[1]-1] - i[2] < amount:
        amount = ref[i[0]-1] + micro[i[1]-1] - i[2]

print(min(mini, amount))

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
a = list(input().split())
b = list(input().split())
l = []
n = []
for i in range(M):
  x, y, c = map(int, input().split())
  l.append(int(a[x-1])+int(b[y-1])-c)
for k in range(A):
  for m in range(B):
    n.append(int(a[k])+int(b[m]))
print(min(min(l), min(n)))

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# 2次元配列
grid = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    grid.append(array)
    
sum_fee = []
for i in a:
    for j in b:
        sum_fee.append(i+j)

for l, m , n in grid:
    sum_fee.append(a[l-1] + b[m-1] - n)
    
print(min(sum_fee))

Submission status: Time Limit Exceeded

Solution code:
A, B, M = [int(i) for i in input().split(" ")]

a = [int(i) for i in input().split(" ")]
b = [int(i) for i in input().split(" ")]
C = []

for i in range(M):
  c = [int(i) for i in input().split(" ")]
  C.append(c)

m = 1000000

for i in a:
  for j in b:
    cost = i + j
    if m >= cost:
      m = cost

for c in C:
  cost = a[c[0] - 1] + b[c[1] - 1] - c[2]
  if m >= cost:
    m = cost

print(m)

Submission status: Time Limit Exceeded

Solution code:
a,b,m=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)

Submission status: Time Limit Exceeded

Solution code:
import itertools

A,B,M=[int(x) for x in input().split()]

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

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

for i in range(M):
    x,y,c=[int(x) for x in input().split()]
    if waribiki[y-1][x-1] !=0:
        waribiki[y-1][x-1] = max(c,waribiki[y-1][x-1])
    else:
        waribiki[y-1][x-1] = c

ans = 1000000007
for i,j in itertools.product( range(A),range(B)):
    p = a[i]+b[j]-waribiki[j][i]
    if p<ans:
        ans =p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(map(int, input().split(" ")))

a = s[0]
b = s[1]
m = s[2]

a_l = list(map(int, input().split(" ")))
b_l = list(map(int, input().split(" ")))

ans = a_l[0] + b_l[0]

for i in a_l:
    for t in b_l:
        if (i + t) < ans:
            ans = i + t

for i in range(m):
    x = list(map(int, input().split(" ")))
    if ans > (a_l[x[0] - 1] + b_l[x[1] -1] - x[2]):
        ans = a_l[x[0] -1] + b_l[x[1] -1] - x[2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

# input = sys.stdin.readline

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

microwave = list(map(int, input().split()))

refrigerator = list(map(int, input().split()))

Discount = [list(map(int, input().split())) for ii in range(m)]

money = 99999999999
for i, ai in enumerate(microwave):
    for j, bi in enumerate(refrigerator):
        mi = ai + bi
        dis_max = 0
        for dis in Discount:
            if (dis[0] == i+1) and (dis[1] == j+1):
                if dis[2] > dis_max:
                    dis_max = dis[2]
        mi -= dis_max
        if money > mi:
            money = mi
print(money)

Submission status: Time Limit Exceeded

Solution code:
abm = input('')
a = int(abm.split(' ')[0])
b = int(abm.split(' ')[1])
m = int(abm.split(' ')[2])
clist = []
dlist = []
wlist = []
cin = input('')
din = input('')
for i in range(0,a):
  clist.append(int(cin.split(' ')[i]))
for i in range(0,b):
  dlist.append(int(din.split(' ')[i]))
for i in range(0,m):
  win = input('')
  wc = int(win.split(' ')[0])
  wd = int(win.split(' ')[1])
  wp = int(win.split(' ')[2])
  wlist.append([wc,wd,wp])

min_price = -1

for i in range(0,a):
  for j in range(0,b):
    total = clist[i] + dlist[j]
    if min_price == -1:
      min_price = total
    elif total < min_price:
      min_price = total      
    for k in wlist:
      wc = k[0]
      wd = k[1]
      wp = k[2]
      if wc == (i+1) and wd == (j+1):
        total = clist[i] + dlist[j] - wp
        if total < min_price:
          min_price = total

print(min_price)

Submission status: Time Limit Exceeded

Solution code:
A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
p = []
for _ in range(M):
    x,y,c = map(int,input().split())
    p.append(a[x-1]+b[y-1]-c)
for i in range(A):
    for j in range(B):
        p.append(a[i]+b[j])
print(min(p))

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
lenzi=list(map(int,input().split()))
zouko=list(map(int,input().split()))
mPrice = 200000
for i in range(A):
  for j in range(B):
    if lenzi[i]+zouko[j]<mPrice:
      mPrice=lenzi[i]+zouko[j]
for i in range(M):
  x, y, c = map(int, input().split())
  if lenzi[x-1]+zouko[y-1]-c<mPrice:
    mPrice=lenzi[x-1]+zouko[y-1]-c
print(mPrice)

Submission status: Time Limit Exceeded

Solution code:
abm = input('')
a = int(abm.split(' ')[0])
b = int(abm.split(' ')[1])
m = int(abm.split(' ')[2])
clist = []
dlist = []
wlist = []
cin = input('')
din = input('')
for i in range(0,a):
  clist.append(int(cin.split(' ')[i]))
for i in range(0,b):
  dlist.append(int(din.split(' ')[i]))
for i in range(0,m):
  win = input('')
  wc = int(win.split(' ')[0])
  wd = int(win.split(' ')[1])
  wp = int(win.split(' ')[2])
  wlist.append([wc,wd,wp])

min_price = -1
for i in range(0,a):
  for j in range(0,b):
    total = clist[i] + dlist[j]
    if min_price == -1:
      min_price = total
    elif total < min_price:
      min_price = total
      total = clist[i] + dlist[j] - wp

for i in range(0,a):
  for j in range(0,b):
    for k in wlist:
      wc = k[0]
      wd = k[1]
      wp = k[2]
      if wc == (i+1) and wd == (j+1):
        total = clist[i] + dlist[j] - wp
        if total < min_price:
          min_price = total

print(min_price)

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 200000

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

for aa in a:
    for bb in b:
        ans = min(ans, aa + bb)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
aa, bb, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(m):
  x1, y1, c1 = list(map(int,input().split()))
  x.append(x1)
  y.append(y1)
  c.append(c1)

price = []
  
for i in range(aa):
  price1 = a[i] + min(b)
  price.append(price1)
  
for i in range(m):
  price.append(a[x[i] - 1] + b[y[i] - 1] - c[i])
  
print(min(price))

Submission status: Time Limit Exceeded

Solution code:
a,b,m=map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
t=[[0,0,0] for i in range(m)]
for i in range(m):
    a, b,c = map(int, input().split())
    t[i][0]=a
    t[i][1]=b
    t[i][2]=c
k=A[0]+B[0]
for i in range(a):
    for j in range(b):
        if A[i]+B[j]<k:
            k=A[i]+B[j]
for i in range(m):
    if A[t[i][0]-1]+B[t[i][1]-1]-t[i][2]<k:
        k=A[t[i][0]-1]+B[t[i][1]-1]-t[i][2]
print(k)

Submission status: Time Limit Exceeded

Solution code:
A,B,M=[int(x) for x in input().split()]

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

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

for i in range(M):
    x,y,c=[int(x) for x in input().split()]
    if waribiki[y-1][x-1] !=0:
        waribiki[y-1][x-1] = max(c,waribiki[y-1][x-1])
    else:
        waribiki[y-1][x-1] = c

ans = 1000000007
for i in range(A):
    for j in range(B):
        p = a[i]+b[j]-waribiki[j][i]
        if p<ans:
            ans =p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B, M = 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 = 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))

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
a = list(input().split())
b = list(input().split())
l = []
n = []
for i in range(M):
  x, y, c = map(int, input().split())
  l.append(int(a[x-1])+int(b[y-1])-c)
l.sort()
for k in range(A):
  for m in range(B):
    n.append(int(a[k])+int(b[m]))
n.sort()
print(min(l[0],n[0]))

Submission status: Time Limit Exceeded

Solution code:
a, b, m = map(int, input().split())
ref = list(map(int, input().split()))
micro = list(map(int, input().split()))
tk = [list(map(int, input().split())) for i in range(m)]

amount = set()
for i in range(a):
    for j in range(b):
        amount.add(ref[i] + micro[j])


for i in tk:
    amount.add(ref[i[0]-1] + micro[i[1]-1] - i[2])

print(min(amount))

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
a_price = list(map(int, input().split()))
b_price = list(map(int, input().split()))
coupon = [list(map(int, input().split())) for i in range(M)]
min = a_price[0] + b_price[0]
for i in a_price:
    for j in b_price:
        if min > i+j:
            min = i+j

for cpn in coupon:
    idx_a = cpn[0]-1
    idx_b = cpn[1]-1
    total = a_price[idx_a] + b_price[idx_b] - cpn[2]
    if min > total:
        min = total

print(min)

Submission status: Time Limit Exceeded

Solution code:
[A, B, M] = [int(i) for i in input().split()]
a_list = [int(i) for i in input().split()]
b_list = [int(i) for i in input().split()]
min_amount = 2*10**5
for a in range(A):
  for b in range(B):
    amount = a_list[a] + b_list[b]
    min_amount = min(amount, min_amount)
for m in range(M):
  [x, y, c] = [int(i) for i in input().split()]
  amount = a_list[x-1] + b_list[y-1] - c
  min_amount = min(amount, min_amount)
print(min_amount)

Submission status: Time Limit Exceeded

Solution code:
As, Bs, Ms = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

mm = [[0 for i in range(Bs)] for j in range(As)]
for i in range(Ms):
  a, b, c = map(int, input().split())
  if c > mm[a-1][b-1]:
    mm[a-1][b-1] = c

ans = 1000000
for i,a in enumerate(A):
  for j,b in enumerate(B):
    if ans > a+b-mm[i][j]:
      ans = a+b-mm[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
a = list(input().split())
b = list(input().split())
l = []
for i in range(M):
  x, y, c = map(int, input().split())
  l.append(int(a[x-1])+int(b[y-1])-c)
for k in range(A):
  for m in range(B):
    l.append(int(a[k])+int(b[m]))
l.sort()
print(l[0])

Submission status: Time Limit Exceeded

Solution code:
a, b, m = 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))

Submission status: Time Limit Exceeded

Solution 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()

Submission status: Time Limit Exceeded

Solution code:
na,nb,nm = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
TA = []
for i in range(nm):
    m1, m2, m3 = map(int,input().split())
    T = a[m1-1]+b[m2-1]-m3
    TA.append(T)
for i in range(na):
    for j in range(nb):
        T = a[i] + b[j]
        TA.append(T)
print(min(TA))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))

    ret = 10**12
    for x in range(a):
        for y in range(b):
            ret = min(ret, A[x]+B[y]-XYC.get((x, y), 0))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
na,nb,nm = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
TA = []
for i in range(nm):
    m1, m2, m3 = map(int,input().split())
    T = a[m1-1]+b[m2-1]-m3
    TA.append(T)
for i in range(na):
    for j in range(nb):
        T = a[i] + b[j]
        TA.append(T)
TA = (sorted(TA))
print(TA[0])

Submission status: Time Limit Exceeded

Solution code:
import itertools

a, b, m = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
m_list = [list(map(int, input().split())) for _ in range(m)]
kumiawase_kingaku = float('inf')
for ab in itertools.product(a_list, b_list):
    if ab[0] + ab[1] < kumiawase_kingaku:
        kumiawase_kingaku = ab[0] + ab[1]

for x, y, c in m_list:
    reizouko = a_list[x-1]
    denshirenji = b_list[y-1]
    kingaku = reizouko + denshirenji - c
    if kingaku < kumiawase_kingaku:
        kumiawase_kingaku = kingaku

print(kumiawase_kingaku)

Submission status: Time Limit Exceeded

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

A, B, M = 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 = 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)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
A,B,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = [0 for _ in range(m)]
y = [0 for _ in range(m)]
c = [0 for _ in range(m)]
for i in range(m):
    x[i],y[i],c[i] = map(int,input().split())

ans = 10000000000

for i in range(A):
    for j in range(B):
        for k in range(m):
            if(i+1 == x[k] and j+1 == y[k]):
                price = a[i] + b[j] - c[k]
            else:
                price = a[i] + b[j]
            ans = min(ans,price)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

a, b, m = MAP()
A = LIST()
B = LIST()

L = [LIST() for i in range(m)]

D = [[0] * b for i in range(a)]
for x,y,c in L:
    D[x-1][y-1] = max(D[x-1][y-1], c)


ans = INF
C = [[0] * b for i in range(a)]
for i in range(a):
    for j in range(b):
        ans = min(A[i] + B[j] - D[i][j], ans)
        
print(ans)

# exit()

# for x, y, c in L:
#     C[x-1][y-1] = min(C[x-1][y-1], C[x-1][y-1]-c)

# print(min(C))


# #     ans.append(A[x-1] + B[y-1] - c)
# # print(min(ans))



# exit()
# s = input()
# m= "hi"
# # for i in range():
# l = len(s) // 2
# if l * m == s:
#     print("Yes")
# else:
#     print("No")

# # if s // 2

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
#import numpy as np
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#S = str(input())

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

#割引券を使う場合
ans = sys.maxsize
for _ in range(M) :
  x, y, c = map(int, input().split())
  ans = min(ans, a[x-1]+b[y-1]-c)

#その他の組み合わせ
for i in range(A) :
  for j in range(B) :
    ans = min(ans, a[i] + b[j])

print (ans)

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

m = []

for i in range(M):
    x, y, z = map(int, input().split())
    m.append([x, y, z])

m.sort(reverse = True,key = lambda x: x[2])

h = 100000
for i in a:
    for j in b:
        if i + j < h:
            h = i + j

ans = 100000
if a[m[0][0]-1] + b[m[0][1]-1] - m[0][2] > h:
    ans = h
else:
    ans = a[m[0][0]-1] + b[m[0][1]-1] - m[0][2]

print(ans)