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

h,w,k=map(int,input().split())

y1,x1,y2,x2=map(int,input().split())

maze=[list(input()) for _ in range(h)]

from collections import deque
stack=deque([(y1-1,x1-1)])

def pri(x):
    print("MAZE###########")
    for item in x:
        print(item)

maze[y1-1][x1-1]=0
#pri(maze)
while len(stack)>0:
    #print(stack)
    (y,x)=stack.popleft()
    if (y,x)==(y2-1,x2-1):
        print(maze[y][x])
        exit()

    #縦横左右
    for (my,mx) in [(1,0),(0,1),(-1,0),(0,-1)]:
        #print(my,mx)
        flag=0
        for kk in range(1,k+1):
            ny=y+my*kk
            nx=x+mx*kk
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]!="@":
                    if maze[ny][nx]==".":
                        maze[ny][nx]=maze[y][x]+1
                        stack.append((ny,nx))
                else:
                    break
            else:
                break
    #pri(maze)
print(-1)


### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    #maze=[]
    #for _ in range(h):
    #    maze.append(tuple(input()))

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        #pri(dis)
                    else:
                        break
                else:
                    break

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

import re
N = int(input())
al = "abcdefghijklmnopqrftuvwxyz"
S = []
for n in range(N):
    s = input()
    S.append(''.join(sorted(s)))

# print (S)
cnt = 0
for n in range(N):
    cnt += S[n:].count(S[n])

print (cnt - N)


### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(N)]

# print(S)

D = {}
for s in S:
    if not(s in D.keys()):
        D[s] = 1
    else:
        # print(s)
        D[s] += 1


cnt = 0
for c in D.values():
    if c != 1:
        cnt += (c * (c - 1)) // 2

print (cnt)
### BUGGY CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7
pow2 = [(2 ** i) % mod for i in range(N + 1)]

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0
def dfs(node, parent):
    global ans
    cnt = 1
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    return cnt

dfs(0, None)

ans = ans - N * pow2[N-1] + pow2[N] - 1
ans = ans * pow(pow2[N], mod - 2, mod) % mod

print(ans)

### FIXED CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7

pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0

def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

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

n = int(input())
a = list(map(int,input().split()))
MAX = 10**6+5

divs = [[] for _ in range(MAX)]
cnt = [0]*MAX

for i in range(2,n):
  m = i
  while m < MAX:
    divs[m].append(i)
    m += i
    
pair = True
setwise = True

for i in range(n):
  for d in divs[a[i]]:
    if cnt[d] > 0:
      pair = False
    cnt[d] += 1
    
if pair:
  print('pairwise coprime')
else:
  for i in range(MAX):
    if cnt[i] == n:
      setwise = False
      break
  if setwise:
    print('setwise coprime')
  else:
    print('not coprime')

### FIXED CODE ###

import math

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

MAX = 1000005
c = [0]*MAX

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

pair = True

for i in range(2,MAX):
  cnt = 0
  for j in range(i,MAX,i):
    cnt += c[j]
  if cnt > 1:
    pair = False

if pair:
  print('pairwise coprime')
else:
  g = a[0]
  for i in range(1,n):
    g = math.gcd(g,a[i])
    
  if g == 1:
    print('setwise coprime')
  else:
    print('not coprime')
### BUGGY CODE ###

from collections import deque
h, w = list(map(int, input().split()))
board = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            q.append((i,j, 0))
            board[i][j] = "."

dx=[1,0,-1,0]
dy=[0,1,0,-1]

while q:
    i,j,cnt = q.popleft()
    if board[i][j] != ".":
        continue
    board[i][j] = cnt
    for x, y in zip(dx,dy):
        if 0<=i+x<h and 0<=j+y<w:
            q.append((i+x, j+y, cnt+1))
ans = 0
for i in range(h):
    ans = max(ans, max(board[i]))
print(ans)

### FIXED CODE ###

from collections import deque
dx=[1,0,-1,0]
dy=[0,1,0,-1]

h, w = list(map(int, input().split()))
board = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            board[i][j] = True
            q.append((i, j, 0))
        else:
            board[i][j] = False

ans = 0
while q:
    i,j,cnt = q.popleft()
    for x, y in zip(dx,dy):
        if 0<=i+x<h and 0<=j+y<w and not board[i+x][j+y]:
            board[i+x][j+y] = True
            q.append((i+x, j+y, cnt+1))
            ans = max(ans, cnt+1)
print(ans)
### BUGGY CODE ###

import sys
from queue import *
sys.setrecursionlimit(10**7)

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

adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
"""
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
"""
used = [0 for i in range(n+1)]
que = Queue()
que.put(1)
while que.qsize() != 0:
    m = que.get()
    used[m] = 1
    for i in adjacent_list[m]:
        if not used[i]:
            tree_value[i] += tree_value[m]
            que.put(i)
for i in range(1,n+1):
    print("{} ".format(tree_value[i]), end = "")


### FIXED CODE ###

import sys
from queue import *
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
"""
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
"""
used = [0 for i in range(n+1)]
que = Queue()
que.put(1)
while que.qsize() != 0:
    m = que.get()
    used[m] = 1
    for i in adjacent_list[m]:
        if not used[i]:
            tree_value[i] += tree_value[m]
            que.put(i)
for i in range(1,n+1):
    print("{} ".format(tree_value[i]), end = "")
### BUGGY CODE ###

N = int(input())
lotteries = []
for i in range(0,N):
    lotteries.append(input())

answer = list()
for i in lotteries:
    if not (answer.__contains__(i)):
        answer.append(i)
    else:
        continue

print(len(answer))

### FIXED CODE ###

N = int(input())
lotteries = []
for i in range(0,N):
    lotteries.append(input())

print(len(set(lotteries)))
### BUGGY CODE ###

n = int(input())
abl = [list(map(int,input().split())) for nesya in range(n)]
al = []
bl = []
for ab in abl:
  al.append(ab[0])
  bl.append(ab[1])
  al.sort()
  bl.sort()
if n%2 == 1:
  z = (n+1)//2-1
  print(bl[z]-al[z]+1)
else:
  x = n//2
  ax2 = al[x-1]+al[x]
  bx2 = bl[x-1]+bl[x]
  print(bx2-ax2+1)

### FIXED CODE ###

from statistics import median

n = int(input())
abl = [list(map(int,input().split())) for nesya in range(n)]
al = []
bl = []
for ab in abl:
  al.append(ab[0])
  bl.append(ab[1])
if n%2 == 1:
  print(median(bl)-median(al)+1)
else:
  print(int(median(bl)*2-median(al)*2+1))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M, K = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [0 for i in range(N)]

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    fre = [set() for _ in range(N)]
    blo = [set() for _ in range(N)]
    mem = {i for i in range(N)}
    for i in [0]*M:
        a, b = (int(i) for i in input().split())
        fre[a-1].add(b-1)
        fre[b-1].add(a-1)
        unite(a-1, b-1)
    for i in [0]*K:
        a, b = (int(i) for i in input().split())
        blo[a-1].add(b-1)
        blo[b-1].add(a-1)
    for i in range(N):
        cur = 0
        for j in mem - fre[i] - {i} - blo[i]:
            if is_same_group(i, j):
                cur += 1
        print(cur, end=" ")
    print()


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M, K = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [0 for i in range(N)]

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    fre = [set() for _ in range(N)]
    blo = [set() for _ in range(N)]
    mem = {i for i in range(N)}
    for i in [0]*M:
        a, b = (int(i) for i in input().split())
        fre[a-1].add(b-1)
        fre[b-1].add(a-1)
        unite(a-1, b-1)
    cur = [-1]*N
    from collections import Counter
    for i, x in enumerate(par):
        unite(i, x)
    c = Counter(par)
    # print(par, is_same_group(5, 7))
    for i in [0]*K:
        a, b = (int(i) for i in input().split())
        if is_same_group(a-1, b-1):
            blo[a-1].add(b-1)
            blo[b-1].add(a-1)
    for i in range(N):
        cur = c[par[i]] - len(fre[i]) - len(blo[i]) - 1
        print(cur, end=" ")
    print()


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

n,m = map(int,input().split())
ahoge = []
hanege = []
for i in range(m):
    ai,bi = map(int,input().split())
    if ai == 1:
        ahoge.append(bi)
    if bi == n:
        hanege.append(ai)
flag = 0
for i in ahoge:
    if i in hanege:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")

### FIXED CODE ###

n,m = map(int,input().split())
ahoge = []
hanege = []
for i in range(m):
    ai,bi = map(int,input().split())
    if ai == 1:
        ahoge.append(bi)
    if bi == n:
        hanege.append(ai)
ahoge.sort()
hanege.sort()
def bis(i):
    under = 0
    upper = len(hanege)-1
    while under <= upper:
        l = (under+upper)//2
        if i == hanege[l]:
            return 1
        elif i < hanege[l]:
            upper = l-1
        elif i > hanege[l]:
            under = l+1
    return 0
flag = 0
for i in ahoge:
    if bis(i) == 1:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())
c = list(map(int,input().split(" ")))
ans = 0

for i in range(n):
    if c[i] == min(c[:i+1]):
        ans += 1
        
print(ans)

### FIXED CODE ###

n = int(input())
c = list(map(int,input().split(" ")))
ans = 0
sai = c[0]
for i in range(n):
    if c[i] <= sai:
        sai = c[i]
        ans += 1
print(ans)
### BUGGY CODE ###

from heapq import heappop, heappush
def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = []
    heappush(que,(0,(x,y)))
    d[x][y] = 0
    while que:
        [num,(qx,qy)] = heappop(que)
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@':
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    heappush(que,[d[nx][ny],(nx,ny)])
    print(d[gx][gy])


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = deque()
    que.append((x,y))
    d[x][y] = 0
    while que:
        (qx,qy) = que.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@' or (d[nx][ny] != -1 and d[nx][ny] < d[qx][qy]+1):
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    que.append((nx,ny))
    print(d[gx][gy])
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

x,y=map(int,input().split())

if x==y:
  print(-1)
elif y==1:
  print(-1)
else:
  for i in range(1,10**10):
    if x*i%y !=0:
      print(x*i)

### FIXED CODE ###

x,y=map(int,input().split())

if x%y==0:
  print(-1)
else:
  print(x)
### BUGGY CODE ###

import numpy as np
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 CO[H-1]=DO[H-1]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=DO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
  else:
   CO[H-k-2]=DO[H-k-2]
 for h in range(W-1):
  if np.amax(CO[:,h])>K:
   E=1000000
   break
  elif np.amax(CO[:,h])<=K and np.amax(np.sum(CO[:,h:h+2],axis=1))>K:
   D+=1
  else:
   CO[:,h+1]=np.sum(CO[:,h:h+2],axis=1)
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K=map(int,input().split())
CO=[[0 for i in [0]*W] for j in [0]*H]
DO=[[0 for i in [0]*W] for j in [0]*H]
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
CO[H-1]=DO[H-1]
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 for k in range(H-1):
  if Sui[k]==0:
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]+CO[H-k-1][i]
  else:
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]
 lst=[0]*H
 for h in range(W):
  c=max(CO[x][h] for x in range(H))
  d=max(lst[y]+CO[y][h] for y in range(H))
  if c>K:
   E=1000000
   break
  elif d>K:
   D+=1
   lst=[0]*H
  for z in range(H):
   lst[z]+=CO[z][h]
 F=min(F,D+E)
print(F)
### BUGGY CODE ###

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D
sample_input = list(range(3))
sample_input[0] = '''5
5
1
4
3
2'''
sample_input[1] = '''3
3
2
1'''
sample_input[2] = '''1
1'''
give_sample_input = None
if give_sample_input is not None:
    sample_input_list = sample_input[give_sample_input].split('\n')
    def input():
        return sample_input_list.pop(0)
        
# main
def print_list(l):
    output = ''
    for elem in l:
        output += str(elem) + ' '
    output = output.rstrip()
    print(output)

def log_two_floor(n):
    pot = 1
    power = 0
    while (pot < n):
        pot *= 2
        power += 1
    return power

def insertion_sort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g
        while (j >= 0 and A[j] > v):
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt

def shell_sort(A, n):
    cnt = 0
    m = log_two_floor(n)
    if m == 0:
        print(1)
        print(1)
        print(0)
        return
    print(m)
    G = [2**(m-i-1) for i in range(m)]
    print_list(G)
    for i in range(m):
        cnt += insertion_sort(A, n, G[i])
    print(cnt)
        
num_of_data = int(input())
data = []
for i in range(num_of_data):
    data.append(int(input()))
shell_sort(data, num_of_data)
for d in data:
    print(d)

### FIXED CODE ###

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D
sample_input = list(range(3))
sample_input[0] = '''5
5
1
4
3
2'''
sample_input[1] = '''3
3
2
1'''
sample_input[2] = '''5
5
1
4
3
2'''
give_sample_input = None
if give_sample_input is not None:
    sample_input_list = sample_input[give_sample_input].split('\n')
    def input():
        return sample_input_list.pop(0)
        
# main
def print_list(l):
    output = ''
    for elem in l:
        output += str(elem) + ' '
    output = output.rstrip()
    print(output)

def determine_G(n):
    G = []
    pot = 1
    while True:
        pot *= 2
        if pot-1 > n:
            break
        G.append(pot-1)
    G.reverse()
    return G

def log_m_floor(n):
    m = 2
    pot = 1
    power = 0
    while (pot < n):
        pot *= 2
        power += 1
    return power

def insertion_sort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g
        while (j >= 0 and A[j] > v):
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt

def shell_sort(A, n):
    cnt = 0
    G = determine_G(n)
    m = len(G)
    if m == 0:
        print(1)
        print(1)
        print(0)
        return
    print(m)
    print_list(G)
    for i in range(m):
        cnt += insertion_sort(A, n, G[i])
    print(cnt)
        
num_of_data = int(input())
data = []
for i in range(num_of_data):
    data.append(int(input()))
shell_sort(data, num_of_data)
for d in data:
    print(d)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
su=sum(a)
c=[abs(sum(a[:i+1])-su/2)*2 for i in range(n)]
print(int(min(c)))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
import itertools
b = list(itertools.accumulate(a))
for i in range(n):
  b[i] = abs(2*b[i]-b[-1])
print(min(b))
### BUGGY CODE ###

A, B, M = map(int,input().split())
val_m = [[0] * 3 for i in range(M)]

val_a = list(map(int, input().split()))
val_b = list(map(int, input().split()))

for i in range(M):
  val_m[i][0], val_m[i][1], val_m[i][2] = map(int, input().split())

dis_val = []
for i in range(M):
  dis_val.append(val_a[val_m[i][0]-1] + val_b[val_m[i][1]-1] - val_m[i][2])


val_a = list(set(val_a))
val_b = list(set(val_b))
sum_val = []
for i in range(len(val_a)):
  for j in range(len(val_b)):
    sum_val.append(val_a[i] + val_b[j])


sum_val.extend(dis_val)
sum_val.sort()
print(sum_val[0])

### FIXED CODE ###

A, B, M = map(int,input().split())
val_m = [[0] * 3 for i in range(M)]

val_a = list(map(int, input().split()))
val_b = list(map(int, input().split()))

for i in range(M):
  val_m[i][0], val_m[i][1], val_m[i][2] = map(int, input().split())

dis_val = []
for i in range(M):
  dis_val.append(val_a[val_m[i][0]-1] + val_b[val_m[i][1]-1] - val_m[i][2])

val_a = list(set(val_a))
val_b = list(set(val_b))

val_a.sort()
val_b.sort()
dis_val.sort()

sum_val = val_a[0] + val_b[0]
if(sum_val <= dis_val[0]):
  print(sum_val)
else:
  print(dis_val[0])
### BUGGY CODE ###

x=input().split()
h=int(x[0])
n=int(x[1])
a=[]
b=[]
for k in range(n):
  x=input().split()
  a.append(int(x[0]))
  b.append(int(x[1]))  
m=max(a)  
dp=[10**8]*(h+m)
dp[0]=0
for k in range(h+m):
  for i in range(n):
    if k-a[i]<0:
      continue
    new=dp[k-a[i]]+b[i]
    if new < dp[k]:
      dp[k]=new
print(min(dp[h:h+m]))
      
      
  

### FIXED CODE ###

x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=(dp[k-a]+b).min()
print(dp[h:h+m].min())
### BUGGY CODE ###

def main():
    n = int(input())
    for i in range(n):
        calc(i)
 
def calc(n):
    count = 0
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            for z in range(1, n + 1):
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == n+1:
                     count += 1
    print(count)
    return
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import math
def main():
    n = int(input())
    ans = []
    for x in range(1, int(math.sqrt(n+1))+1):
        for y in range(1, int((math.sqrt(n+1)))+1):
            for z in range(1, int((math.sqrt(n+1)))+1):
                ans.append(x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x)
    counter = Counter(ans)
    for i in range(1, n+1):
        print(counter[i])
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
tmp = []
PY = [[] for _ in range(N + 1)]
# PY_sorted = [[] for _ in range(N + 1)]

for i in range(M):
    p, y = map(int, input().split())
    tmp.append([p, y])
    PY[p].append(y)
    PY[p] = sorted(PY[p])

# for i in range(1, N + 1):
#     PY_sorted[i] = sorted(PY[i])

for prefecture, year in tmp:
    text = ""
    text += "%06d" % prefecture
    text += "%06d" % (PY[prefecture].index(year) + 1)
    print(text)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
PY = [[] for _ in range(N + 1)]

for i in range(M):
    p, y = map(int, input().split())
    PY[p].append((y, i))

ans = []

for pre_id, info in enumerate(PY):
    info.sort()
    for i in range(len(info)):
        ans.append((info[i][1], "%06d" % pre_id, "%06d" % (i + 1)))

ans.sort()
for i, x, y in ans:
    print(str(x) + str(y))