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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from sys import stdin

def calc_ab_price_without_pricedown(a_list, b_list):
    ab_price = [[a_list[j]+b_list[i] for i in range(len(b_list))] for j in range(len(a_list))]
    """
    for i, a_price in enumerate(a_list):
        for j, b_price in enumerate(b_list):
            ab_price[i][j] = a_price + b_price
    """
    return ab_price


def calc_pricedown(ab_price, pricedown_list):
    """値段表から値引きする"""
    for i, j , price in pricedown_list:
        for k, l, price2 in pricedown_list:
            if (i, j) == (k, l) and price >= price2:
                continue
            elif (i, j) == (k, l) and price < price2:
                price = 0

        ab_price[i-1][j-1] -= price

    return ab_price

def calc_min_price(a_list, b_list, ab_price):
    min_price = float('inf')
    for i in range(len(a_list)):
        for j in range(len(b_list)):
            min_price = min(ab_price[i][j], min_price)
    return min_price

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

#a_list = list(map(int, input().split()))
a_list = [int(x) for x in stdin.readline().rstrip().split()]
b_list = [int(x) for x in stdin.readline().rstrip().split()]

pricedown_list = []
for i in range(m):
    pricedown_list.append([int(x) for x in stdin.readline().rstrip().split()])
    # pricedown_list.append((list(map(int, input().split()))))


# 割引せずに購入する場合の合計金額のうち、最低金額を算出
ab_price = calc_ab_price_without_pricedown(a_list, b_list)

# 最低金額を算出
min_price = calc_min_price(a_list, b_list, ab_price)

# 割引の値段を含めて考える
pricedowned_ab = calc_pricedown( ab_price, pricedown_list)

# 値引き後の最低金額を算出
min_pricedown = calc_min_price(a_list, b_list, pricedowned_ab)

print(min(min_price, min_pricedown))

Submission status: Time Limit Exceeded

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

def main():
    fridge_count, microwave_count, coupon_count = map(int, input().split(' '))
    fridges = np.array(list(map(int, input().split(' '))))
    microwaves = np.array(list(map(int, input().split(' '))))
    coupons = []
    for _ in range(coupon_count):
        coupons.append(list(map(int, input().split(' '))))
    # print(fridges, microwaves, coupons)

    prices = set()
    for fridge in set(fridges):
        for microwave in set(microwaves):
            prices.add(fridge + microwave)
    
    for coupon in coupons:
        prices.add(fridges[coupon[0]-1] + microwaves[coupon[1]-1] - coupon[2])
    # print(prices)

    print(min(prices))

    return 0


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

cut_map = [[0*i for i in range(B)] for j in range(A)]
for i in range(M):
    [inx, iny, inc] = list(map(int, input().split()))
    if cut_map[inx-1][iny-1] > -inc:
        cut_map[inx-1][iny-1] = -inc

for i in range(A):
    for j in range(B):
        cut_map[i][j] = cut_map[i][j] + a[i] + b[j]

print(min(min(cut_map)))

Submission status: Time Limit Exceeded

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

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

    totals = []
    for i in a:
        total = [i+j for j in b]   
        totals.append(total)

    res = min(a) + min(b)
    for m in grid:
        if m[0]-1 < A and m[1]-1 < B:
            tmp = totals[m[0]-1][m[1]-1] - m[2]
    
            if tmp < res:
                res = tmp

    print(res)
    
resolve()

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] * M
y = [0] * M
c = [0] * M

min = 99999999

calced = []

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

k = 0

for i in range(A):
    for j in range(B):
        if calced[k][0] == i & calced[k][1] == j:
            k = k + 1
            if k == M:
                k = 0
            continue;
        cost = a[i] + b[j]
        if cost < min:
            min = cost

print(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()]

x = [0] * M
y = [0] * M
c = [0] * M

ans = []

for i in range(M):
    x[i], y[i], c[i] = [int(k) for k in input().split()]

temp = list(itertools.product(a, b))
for i,j in temp:
    ans.append(i+j)


for i in range(M):
    ans.append(a[x[i]-1] + b[y[i]-1] - c[i])

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from sys import stdin

def calc_ab_price_without_pricedown(a_list, b_list):
    ab_price = [[[] for i in range(len(b_list))] for j in range(len(a_list))]
    for i, a_price in enumerate(a_list):
        for j, b_price in enumerate(b_list):
            ab_price[i][j] = a_price + b_price

    return ab_price


def calc_pricedown(ab_price, pricedown_list):
    """値段表から値引きする"""
    for i, j , price in pricedown_list:
        for k, l, price2 in pricedown_list:
            if (i, j) == (k, l) and price >= price2:
                continue
            elif (i, j) == (k, l) and price < price2:
                price = 0

        ab_price[i-1][j-1] -= price

    return ab_price

def calc_min_price(a_list, b_list, ab_price):
    min_price = float('inf')
    for i in range(len(a_list)):
        for j in range(len(b_list)):
            min_price = min(ab_price[i][j], min_price)
    return min_price

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

#a_list = list(map(int, input().split()))
a_list = [int(x) for x in stdin.readline().rstrip().split()]
b_list = [int(x) for x in stdin.readline().rstrip().split()]

pricedown_list = []
for i in range(m):
    pricedown_list.append([int(x) for x in stdin.readline().rstrip().split()])
    # pricedown_list.append((list(map(int, input().split()))))


# 割引せずに購入する場合の合計金額のうち、最低金額を算出
ab_price = calc_ab_price_without_pricedown(a_list, b_list)

# 最低金額を算出
min_price = calc_min_price(a_list, b_list, ab_price)

# 割引の値段を含めて考える
pricedowned_ab = calc_pricedown( ab_price, pricedown_list)

# 値引き後の最低金額を算出
min_pricedown = calc_min_price(a_list, b_list, pricedowned_ab)

print(min(min_price, min_pricedown))

Submission status: Time Limit Exceeded

Solution code:
abm = input('')
a = int(abm.split(' ')[0])
b = int(abm.split(' ')[1])
m = int(abm.split(' ')[2])
wdic = {}
pdic = {}
clist = input('').split(' ')
dlist = input('').split(' ')

# 冷蔵庫価格辞書の作成
cdic = {}
max_c = 0
for i in range(0,a):
  cdic[i+1] = int(clist[i])
cdic = sorted(cdic.items(), key=lambda x:x[1])

# 電子レンジ価格辞書の作成
ddic = {}
for i in range(0,b):
  ddic[i+1] = int(dlist[i])
ddic = sorted(ddic.items(), key=lambda x:x[1])

# 割引辞書の作成
for i in range(0,m):
  win = input('').split(' ')
  wc = win[0]
  wd = win[1]
  wkey = wc + "-" + wd # 割引キー
  wp = int(win[2]) # 割引価格  
  if wkey in wdic.keys():
    if wp > wdic[wkey]:
      wdic[wkey] = wp
  else:
    wdic[wkey] = wp

max_w = max(wdic.values())

# 価格表組み合わせの作成
min_price = -1
for c in cdic:
  for d in ddic:
    key = str(c[0]) + "-" + str(d[0])
    val = int(c[1]) + int(d[1])
    w = 0
    if key in wdic.keys():
      w = wdic[key]
    # 商品金額の合計が最大割引額を考えてもオーバーする場合、終了
    price = val - w
    if min_price == -1:
      min_price = price
    elif price < min_price:
      min_price = price
    pdic[key] = price
    if (val - max_w) > min_price:
      break

# 割引後価格でソート
#pdic2 = sorted(pdic.items(), key=lambda x:x[1])
# ソート結果の1件目の値が最安値
# print(pdic2)
print(min_price)

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
X = list(map(int,input().split()))
Y = list(map(int,input().split()))
C = [list(map(int,input().split())) for l in range(M)]



total = []
for i in range(len(X)):
    for j in range(len(Y)):
        for k in range(len(C)):
            if i+1 == C[k][0] and j+1 == C[k][1]:
                    total.append(X[i] + Y[j] - C[k][2])
            else:
                 total.append(X[i]+Y[j])


total_min = min(total)

print(total_min)

Submission status: Time Limit Exceeded

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

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

cut_map = [[0*i for i in range(B)] for j in range(A)]
for i in range(M):
    [inx, iny, inc] = list(map(int, input().split()))
    if cut_map[inx-1][iny-1] > -inc:
        cut_map[inx-1][iny-1] = -inc

cost_map = [[0*i for i in range(B)] for j in range(A)]
for i in range(A):
    for j in range(B):
        cost_map[i][j] = a[i] + b[j] + cut_map[i][j]

print(min(min(cost_map)))

Submission status: Time Limit Exceeded

Solution code:
A, B, M = map(int, input().split())
Ma = [int(_) for _ in input().split()]
Mb = [int(_) for _ in input().split()]
Mm = [[int(_) for _ in input().split()] for __ in range(M)]

r = 10 ** 5
for i in range(A):
  for j in range(B):
    c = max([z for x,y,z in Mm if x == i+1 and y == j+1], default=0)
    r = min(r, Ma[i] + Mb[j] - c)
print(r)

Submission status: Time Limit Exceeded

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


sum = []
for i in range(A):
  for j in range(B):
    sum.append(int(a[i])+int(b[j]))

for i in range(M):
  X = int(XYc[i][0])
  Y = int(XYc[i][1])
  c = int(XYc[i][2])
  sum.append(int(a[X-1])+int(b[Y-1])-c)
  
    
print(min(sum))

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

x = [0] * M
y = [0] * M
c = [0] * M

ans = []

for i in range(M):
    x[i], y[i], c[i] = [int(k) for k in input().split()]
for i, j in itertools.product(a, b):
    ans.append(i + j)

for i in range(M):
    ans.append(a[x[i]-1] + b[y[i]-1] - c[i])

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
a, b, m = map(int, input().split())
a1 = list(map(int, input().split()))
b1 = list(map(int, input().split()))

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

import itertools
import numpy as np

b2 = np.array(b1)

a2 = np.array(a1)
a2 = a2.reshape(a,1)

from collections import deque
ans = []
ans = deque(ans)

for i in a1:
    ans.append( np.min( b2 + np.tile(i, b) ) )


for i in range(m):
    ans.append( a1[disc[i][0]-1] + b1[disc[i][1]-1] - disc[i][2] )

ans = list(ans)
print(min( min(ans), np.min(a2+b2) ))

Submission status: Time Limit Exceeded

Solution code:


a,b,m = [int(x) for x in input().split()]
an = [(int(x),i+1) for i,x in enumerate(input().split())]
bn = [(int(x),i+1) for i,x in enumerate(input().split())]

an = sorted(an)
bn = sorted(bn)

discounts = {}
discount_list = []
for i in range(m):
    x,y,c = [int(x) for x in input().split()]
    if (x,y) in discounts and discounts[(x,y)] > c:
        continue
    discounts[(x,y)] = c
    discount_list.append(c)

discount_list = sorted(discount_list,reverse=True)

i = 0
j = 0
min = an[0][0]+bn[0][0]
max_discount = max(discount_list)
len_an = len(an)
len_bn = len(bn)

# print(an)
# print(bn)
# print(min)
# print(discounts)

for ai in an:
    for bj in bn:
        a_index = ai[1]
        b_index = bj[1]
        discount = 0
        if (a_index, b_index) in discounts:
            discount = discounts[(a_index, b_index)]
        total = ai[0] + bj[0] - discount
        if min > total:
            min = total

        if ai[0] + bj[0] - max_discount > min:
            break



# while True:
#     a_index = an[i][1]
#     b_index = bn[j][1]
#     discount = 0
#     if (a_index, b_index) in discounts:
#         discount = discounts[(a_index, b_index)]
#     total = an[i][0] + bn[j][0] - discount
#     if min > total:
#         min = total
#
#     if an[i][0] + bn[j][0] - max_discount > min:
#         break
#     elif i == len_an-1 and j == len_bn-1:
#         break
#     elif i == len_an-1:
#         j += 1
#     elif j == len_bn-1:
#         i += 1
#     else:
#         a_diff = an[i+1][0] - an[i][0]
#         b_diff = bn[j+1][0] - an[j][0]
#         if a_diff < b_diff:
#             i += 1
#         else:
#             j += 1

print(min)

Submission status: Time Limit Exceeded

Solution code:
A, B, M = [int(n) for n in input().split()]
a  = [int(n) for n in input().split()]
b = [int(n) for n in input().split()]
XY = {}
for m in range(M):
    x, y, c = [int(n) for n in input().split()]
    v = XY.setdefault((x-1, y-1), 0)
    XY[(x-1, y-1)] = max(v, c)
ans = 10**5+1
for i, ai in enumerate(a):
    for j, bj in enumerate(b):
        if (i, j) in XY:
            vc = ai + bj - XY[(i, j)]
            if ans > vc:
                ans = vc
        else:
            vc = ai + bj
            if ans > vc:
                ans = vc
print(ans)

Submission status: Time Limit Exceeded

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

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

x = []
y = []
c = []
x_append = x.append
y_append = y.append
c_append = c.append

for i in range(M):
    [inx, iny, inc] = list(map(int, input().split()))
    x_append(inx)
    y_append(iny)
    c_append(inc)

cut_map = [[0*i for i in range(B)] for j in range(A)]
for i in range(M):
    if cut_map[x[i]-1][y[i]-1] > -c[i]:
        cut_map[x[i]-1][y[i]-1] = -c[i]

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

for i in range(A):
    for j in range(B):
        cost_map[i][j] = a[i] + b[j] + cut_map[i][j]

print(min(min(cost_map)))

Submission status: Time Limit Exceeded

Solution code:
abm = input('')
a = int(abm.split(' ')[0])
b = int(abm.split(' ')[1])
m = int(abm.split(' ')[2])
wdic = {}
pdic = {}
clist = input('').split(' ')
dlist = input('').split(' ')

# 冷蔵庫価格辞書の作成
cdic = {}
max_c = 0
for i in range(0,a):
  cdic[i+1] = int(clist[i])
cdic = sorted(cdic.items(), key=lambda x:x[1])

# 電子レンジ価格辞書の作成
ddic = {}
for i in range(0,b):
  ddic[i+1] = int(dlist[i])
ddic = sorted(ddic.items(), key=lambda x:x[1])

# 割引辞書の作成
for i in range(0,m):
  win = input('').split(' ')
  wc = win[0]
  wd = win[1]
  wkey = wc + "-" + wd # 割引キー
  wp = int(win[2]) # 割引価格  
  if wkey in wdic.keys():
    if wp > wdic[wkey]:
      wdic[wkey] = wp
  else:
    wdic[wkey] = wp

max_w = max(wdic.values())

# 価格表組み合わせの作成
min_price = -1
for c in cdic:
  for d in ddic:
    key = str(c[0]) + "-" + str(d[0])
    val = int(c[1]) + int(d[1])
    w = 0
    if key in wdic.keys():
      w = wdic[key]
    price = val - w
    if min_price == -1:
      min_price = price
    elif price < min_price:
      min_price = price
    if price - max_w > min_price:
      break;
    pdic[key] = price

# 割引後価格でソート
pdic2 = sorted(pdic.items(), key=lambda x:x[1])
# ソート結果の1件目の値が最安値
# print(pdic2)
print(pdic2[0][1])

Submission status: Time Limit Exceeded

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

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] * M
y = [0] * M
c = [0] * M

min = 99999999

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

for i in range(A):
    if a[i] > cost:
        continue
    for j in range(B):
        if b[j] > cost:
            break
        cost = a[i] + b[j]
        if cost < min:
            min = cost

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

x = []
y = []
c = []

for i in range(M):
    xi,yi,ci = map(int, input().split())
    x.append(xi)
    y.append(yi)
    c.append(ci)

nesage = b
key = [-1] * B
kingaku = [-1] * A

for j in range(1,A+1):
    coupon = [id for id, x in enumerate(x) if x == j]
    for k in coupon:
        if key[y[k]-1] == -1:
            nesage[y[k]-1] = b[y[k]-1] - c[k]
            key[y[k]-1] = k
        else:
            if c[key[y[k]-1]] < c[k]:
                nesage[y[k]-1] = b[y[k]-1] + c[key[y[k]-1]] - c[k]
                key[y[k]-1] = k
    kingaku[j-1] = a[j-1] + min(nesage)

print(min(kingaku))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import math


def calc_ab_price_without_pricedown(a_list, b_list):
    ab_price = [[[] for i in range(len(b_list))] for j in range(len(a_list))]
    for i, a_price in enumerate(a_list):
        for j, b_price in enumerate(b_list):
            ab_price[i][j] = a_price + b_price

    return ab_price


def calc_pricedown(ab_price, pricedown_list):
    """値段表から値引きする"""
    for i, j , price in pricedown_list:
        for k, l, price2 in pricedown_list:
            if (i, j) == (k, l) and price == price2:
                continue
            elif (i, j) == (k, l) and price < price2:
                price = 0
            elif (i, j) == (k, l) and price > price2:
                continue

        ab_price[i-1][j-1] -= price

    return ab_price

def calc_min_price(a_list, b_list, ab_price):
    min_price = float('inf')
    for i in range(len(a_list)):
        for j in range(len(b_list)):
            min_price = min(ab_price[i][j], min_price)
    return min_price

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

a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

pricedown_list = []
for i in range(m):
    pricedown_list.append((list(map(int, input().split()))))


# 割引せずに購入する場合の合計金額のうち、最低金額を算出
ab_price = calc_ab_price_without_pricedown(a_list, b_list)

# 最低金額を算出
min_price = calc_min_price(a_list, b_list, ab_price)

# 割引の値段を含めて考える
pricedowned_ab = calc_pricedown( ab_price, pricedown_list)

# 値引き後の最低金額を算出
min_pricedown = calc_min_price(a_list, b_list, pricedowned_ab)

print(min(min_price, min_pricedown))

Submission status: Time Limit Exceeded

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

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

x = []
y = []
c = []
for i in range(M):
    [inx, iny, inc] = list(map(int, input().split()))
    x.append(inx)
    y.append(iny)
    c.append(inc)

cut_map = [[0*i for i in range(B)] for j in range(A)]
for i in range(M):
    if cut_map[x[i]-1][y[i]-1] > -c[i]:
        cut_map[x[i]-1][y[i]-1] = -c[i]

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

for i in range(A):
    for j in range(B):
        cost_map[i][j] = a[i] + b[j] + cut_map[i][j]

print(min(min(cost_map)))

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

x = [0] * M
y = [0] * M
c = [0] * M

ans = []

for i in range(M):
    x[i], y[i], c[i] = [int(k) for k in input().split()]
for i in a:
    for j in b:
        ans.append(i + j)

for i in range(M):
    ans.append(a[x[i]-1] + b[y[i]-1] - c[i])

print(min(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()))

x = [0] * M
y = [0] * M
c = [0] * M

min = 99999999

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

for i in range(A):
    if a[i] > cost:
        continue
    for j in range(B):
        if b[j] > cost:
            continue
        cost = a[i] + b[j]
        if cost < min:
            min = cost

print(min)

Submission status: Time Limit Exceeded

Solution code:
a, b, m = map(int, input().split())
a1 = list(map(int, input().split()))
b1 = list(map(int, input().split()))

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

import itertools
import numpy as np

b2 = np.array(b1)

ans = []
from collections import deque
ans = deque(ans)

for i in a1:
    ans.append( np.min( b2 + np.tile(i, b) ) )


for i in range(m):
    ans.append( a1[disc[i][0]-1] + b1[disc[i][1]-1] - disc[i][2] )

ans = list(ans)
print(min(ans))

Submission status: Time Limit Exceeded

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

def main():
    fridge_count, microwave_count, coupon_count = map(int, input().split(' '))
    fridges = np.array(list(map(int, input().split(' '))))
    microwaves = np.array(list(map(int, input().split(' '))))
    coupons = []
    for _ in range(coupon_count):
        coupons.append(list(map(int, input().split(' '))))
    # print(fridges, microwaves, coupons)

    prices = set()
    for fridge in fridges:
        for microwave in microwaves:
            prices.add(fridge + microwave)
    
    for coupon in coupons:
        prices.add(fridges[coupon[0]-1] + microwaves[coupon[1]-1] - coupon[2])
    # print(prices)

    print(min(prices))

    return 0


if __name__ == '__main__':
    main()

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 = 100000
for i in range(m):
	cou[i]=list(map(int, input().split()))
	c=rei[cou[i][0]-1]+den[cou[i][1]-1]-cou[i][2]
	if ans>c:
		ans=c
for i in range(b):
	for j in range(a):
		c=rei[j]+den[i]
		
		if ans>c:
			ans=c
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()))

x = [0] * M
y = [0] * M
c = [0] * M

min = 99999999

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

for i in range(A):
    for j in range(B):
        cost = a[i] + b[j]
        if cost < min:
            min = cost

print(min)

Submission status: Time Limit Exceeded

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

    totals = []
    res = 10000 + 10000
    for i in range(A):
        total = []
        for j in range(B):
            value = a[i]+b[j]
            total.append(value)
            if value < res:
                res = value
        
        totals.append(total)

    for m in grid:
        if m[0]-1 < A and m[1]-1 < B:
            tmp = totals[m[0]-1][m[1]-1] - m[2]
    
            if tmp < res:
                res = tmp

    print(res)
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

lines = sys.stdin.readlines()

# lines = test.strip().split('\n')
num_a ,num_b, num_m = [int(v) for v in lines[0].split()]
# ----

a_list = [int(v) for v in lines[1].split()[:num_a+1]]
b_list = [int(v) for v in lines[2].split()[:num_b+1]]

# print(a_list)
# print(b_list)

# result = max(a_list) + max(b_list)
# # ignores = set()
# for c in lines[3:num_m+3]:
#     a_i, b_i, discount = map(int, c.split())
#     try:
# #         ignores.add((int(a_i), int(b_i)))    
#         price = a_list[a_i-1] + b_list[b_i-1] - discount
        
#         if price < result:
#             result = price
#     except IndexError:
#         print('------')
#         print(c)
#         pass

res1 = [
    a_list[a_i-1]+b_list[b_i-1]-discount for a_i, b_i, discount in [map(int, l.split())  for l in lines[3:num_m+3]]]


res2 = [a+b for b in b_list
        for a in a_list]

print(min(min(res1), min(res2)))

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])

for j in m[:min(len(a),len(b)+1)]:
    if a[j[0]-1] + b[j[1]-1] - j[2] >= 0 and a[j[0]-1] + b[j[1]-1] - j[2] < min(a) + min(b):
        print(a[j[0]-1] + b[j[1]-1] - j[2])
        exit()

print(min(a) + min(b))

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 = []
for i in range(0, m):
    x.append(list(map(int, input().split())))

min = 1000

for j in range(0, len(a)):
    for k in range(0, len(b)):
        ttm = a[j] + b[k]
        if min > ttm:
            min = ttm
    
for l in range(0, len(x)):
    p = x[l][0]
    q = x[l][1]
    tmp = a[p-1]+b[q-1]-x[l][2] 
    if min > tmp:
        min = tmp

print(min)

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(key = lambda x: x[2], reverse=True)


for j in m[:min(len(a),len(b)+1)]:
    if a[j[0]-1] + b[j[1]-1] - j[2] >= 0 and a[j[0]-1] + b[j[1]-1] - j[2] < min(a) + min(b):
        print(a[m[0][0]-1] + b[m[0][1]-1] - m[0][2])
        exit()

print(min(a) + min(b))

Submission status: Time Limit Exceeded

Solution code:
abm = input('')
a = int(abm.split(' ')[0])
b = int(abm.split(' ')[1])
m = int(abm.split(' ')[2])
wdic = {}
pdic = {}
clist = input('').split(' ')
dlist = input('').split(' ')

# 割引辞書の作成
for i in range(0,m):
  win = input('').split(' ')
  wc = win[0]
  wd = win[1]
  wkey = wc + "-" + wd # 割引キー
  wp = int(win[2]) # 割引価格  
  if wkey in wdic.keys():
    if wp > wdic[wkey]:
      wdic[wkey] = wp
  else:
    wdic[wkey] = wp

# 価格表組み合わせの作成
min_price = -1
for i in range(0,a):
  for j in range(0,b):
    key = str(i+1) + "-" + str(j+1)
    val = int(clist[i]) + int(dlist[j])
    w = 0
    if key in wdic.keys():
      w = wdic[key]
    price = val - w
    pdic[key] = price

# 割引後価格でソート
pdic2 = sorted(pdic.items(), key=lambda x:x[1])
# ソート結果の1件目の値が最安値
# print(pdic2)
print(pdic2[0][1])

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()))
z = [list(map(int, input().split())) for _ in range(M)]
mem = []

for i in range(len(a)):
    for j in range(len(b)):
        mem.append(a[i] + b[j])

for x, y, c in z:
    mem.append(a[x - 1] + b[y - 1] - c)

print(min(mem))

Submission status: Time Limit Exceeded

Solution code:
frege_count, oven_count, coupon_count = map(int,input().split())	
frege_prices = list(map(int,input().split()))	
oven_prices = list(map(int,input().split()))	
coupon_list = [list(map(int, input().split())) for i in range(coupon_count)]

minprice = 200000
for f in range(frege_count):
  for o in range(oven_count):
      total_cost = frege_prices[f] +  oven_prices[o]
      if minprice > total_cost:
          minprice = total_cost
for coupon in coupon_list:
  total_cost = frege_prices[coupon[0]-1] + oven_prices[coupon[1]-1] - coupon[2]
  if minprice > total_cost:
          minprice = total_cost
print(minprice)

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(key = lambda x: x[2], reverse=True)


for j in m:
    if a[j[0]-1] + b[j[1]-1] - j[2] >= 0 and a[j[0]-1] + b[j[1]-1] - j[2] < min(a) + min(b):
        print(a[m[0][0]-1] + b[m[0][1]-1] - m[0][2])
        exit()

print(min(a) + min(b))

Submission status: Time Limit Exceeded

Solution code:
abm = input('')
a = int(abm.split(' ')[0])
b = int(abm.split(' ')[1])
m = int(abm.split(' ')[2])
wdic = {}
pdic = {}
clist = input('').split(' ')
dlist = input('').split(' ')

# 割引辞書の作成
for i in range(0,m):
  win = input('').split(' ')
  wc = win[0]
  wd = win[1]
  wkey = wc + "-" + wd # 割引キー
  wp = int(win[2]) # 割引価格  
  if wkey in wdic.keys():
    if wp > wdic[wkey]:
      wdic[wkey] = wp
  else:
    wdic[wkey] = wp

# 価格表組み合わせの作成
min_price = -1
for i in range(0,a):
  for j in range(0,b):
    key = str(i+1) + "-" + str(j+1)
    val = int(clist[i]) + int(dlist[j])
    w = 0
    if key in wdic.keys():
      w = wdic[key]
    price = val - w
    if min_price == -1:
      min_price = price
      pdic[key] = price
    elif price < min_price:
      pdic[key] = price

# 割引後価格でソート
pdic2 = sorted(pdic.items(), key=lambda x:x[1])
# ソート結果の1件目の値が最安値
# print(pdic2)
print(pdic2[0][1])

Submission status: Time Limit Exceeded

Solution code:
p = []
list1 = input()
a = input()
b = input()
list_1 = list(map(int, list1.split(" ")))
alist = list(map(int, a.split(" ")))
blist = list(map(int, b.split(" ")))
A = list_1[0]
B = list_1[1]
M = list_1[2]

for d in range(M):
  l = input()
  xyc = list(map(int, l.split(" ")))
  x = xyc[0]-1
  y = xyc[1]-1
  c = xyc[2]
  for i in range(A):
    for j in range(B):
      p.append(alist[i]+blist[j])
      if x == i and y == j:
        p.append(alist[i]+blist[j]-c)
    	
print(min(p))