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

H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

cache = {}

def calc(x, y):
    if (x, y) in cache:
        return cache[(x, y)]
    p1 = pos[x]
    p2 = pos[y]
    r = abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    cache[(x, y)] = r
    return r

def calclr(l, r):
    if (l, r) in cache:
        return cache[(l, r)]
    result = 0
    x = l
    while x < r:
        y = x + D
        result += calc(x, y)
        x += D
    cache[(l, r)] = result
    return result

for l, r in LR:
    print(calclr(l, r))


### FIXED CODE ###

H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 + 1 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

dt = [0] * (H * W + 1)
for x in range(1, D + 1):
    r = 0
    while 1:
        dt[x] = r
        y = x + D
        if y > H * W:
            break
        p1 = pos[x]
        p2 = pos[y]
        r += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x = y

for l, r in LR:
    print(dt[r] - dt[l])
### BUGGY CODE ###

import collections
n=int(input())
a=[int(input()) for i in range(n)]
c=collections.Counter(a)
ct=0
for j in range(len(set(a))):
  if c.most_common()[j][1]%2==1:
    ct+=1
print(ct)

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
a=sorted(a)
x=a[0]
c=1
ct=0
for i in range(1,n):
  if a[i]==x:
    c+=1
    if i==n-1:
      if c%2==1:
        ct+=1
  else:
    if c%2==1:
      ct+=1
    x=a[i]
    c=1
    if i==n-1:
      ct+=1
print(ct)
### BUGGY CODE ###

from fractions import gcd
mod = 998244353
n,a,b,k = map(int, input().split())
if k % gcd(a,b) != 0:
    print(0)
    exit()
fact = [1]
for i in range(n+10):
    fact.append(fact[-1]*(i+1)%mod)
aaa = fact[n]
for i,j in enumerate(fact):
    fact[i] = pow(j, mod-2, mod)

ans = 0
for i in range(n+1):
    tmp = k-a*i
    if tmp % b:
        continue
    j = tmp//b
    for l in range(max(0, (i+j)-n), min(i,j)+1):
        #print(f"red {i-l}, green {l}, blue {j-l}")
        ans += fact[i-l]*fact[l]*fact[j-l]*fact[n+l-(i+j)]
        ans %= mod
ans = ans*aaa%mod
print(ans)

### FIXED CODE ###

from fractions import gcd

class PERM_COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod

mod = 998244353
hoge = PERM_COMB_MOD(mod=mod)
n,a,b,k = map(int, input().split())
if k % gcd(a,b) != 0:
    print(0)
    exit()
ans = 0
for i in range(n+1):
    tmp = k-a*i
    if tmp % b:
        continue
    j = tmp//b
    if j < 0 or n < j:
        continue
    ans += hoge.comb(n, i)*hoge.comb(n, j)
    ans %= mod
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())

l = set([])
for i in range(len(s)):
  for j in range(i, len(s)):
    l.add(s[i:j+1])
l2 = list(l)
l2.sort()
print(l2[K-1])

### FIXED CODE ###

s = input()
K = int(input())

l = set([])
for i in range(len(s)):
  for j in range(i, min(len(s),i+K)):
    l.add(s[i:j+1])
l2 = list(l)
l2.sort()
print(l2[K-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)
N = int(input()); MOD=pow(10,9)+7
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b);G[b].append(a)
#print(G)
ans = 0

def dfs(v,p): #自分と親
  global ans #ansをGlobal変数として宣言
  res = 1 #戻り値。vを含めた部分木のサイズ。自分の分で最初は1
  ts = [] #vから生えている部分木のリスト
  for u in G[v]:
    if u == p:
      continue
    t = dfs(u,v) #uの部分木のサイズが戻り値
    res += t
    ts.append(t)
  if p != -1: #根以外なら親側の部分木が存在する。
    ts.append(N-res)
  now = pow(2,N-1,MOD) - 1 #自分以外を決めるのが2^(N-1)通り。自分以外が全部0が1通り。
  for x in ts:
    now -= pow(2,x,MOD) - 1 #各部分木に一個以上黒がある場合の数。全通り - 全部白
  ans = (ans+now)%MOD
  return res #vを含めた部分木のサイズ

dfs(0,-1)
ALL = pow(2,N,MOD)
#print(ans,ALL)
ans = ans*pow(ALL,MOD-2,MOD)%MOD #フェルマーの小定理より1/ALL = ALL^(MOD-2)
print(ans)
           

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
N = int(input()); MOD=pow(10,9)+7
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b);G[b].append(a)
#print(G)
ans = 0

def dfs(v,p): #自分と親
  global ans #ansをGlobal変数として宣言
  res = 1 #戻り値。vを含めた部分木のサイズ。自分の分で最初は1
  ts = [] #vから生えている部分木のリスト
  for u in G[v]:
    if u == p:
      continue
    t = dfs(u,v) #uの部分木のサイズが戻り値
    res += t
    ts.append(t)
  if p != -1: #根以外なら親側の部分木が存在する。
    ts.append(N-res)
  now = pow(2,N-1,MOD) - 1 #自分以外を決めるのが2^(N-1)通り。自分以外が全部0が1通り。
  for x in ts:
    now -= pow(2,x,MOD) - 1 #各部分木に一個以上黒がある場合の数。全通り - 全部白
  ans = (ans+now)%MOD
  return res #vを含めた部分木のサイズ

dfs(0,-1)
ALL = pow(2,N,MOD)
#print(ans,ALL)
ans = ans*pow(ALL,MOD-2,MOD)%MOD #フェルマーの小定理より1/ALL = ALL^(MOD-2)
print(ans)
### BUGGY CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
#n=4
#a=8
#x=[7,9,8,9]

#xsum=max(max(x),a)*n
xsum=max(sum(x),a*n)
dp=[[[0]*(xsum+1) for i in range(n+1)] for ii in range(n+1)]

dp[0][0][0]=1

for j in range(1,n+1):
    for k in range(0,n+1):    
        for s in range(0,xsum+1):    
            if s<x[j-1] :
                dp[j][k][s]=dp[j-1][k][s]
            elif s>=x[j-1] and k>=1:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            else:
                dp[j][k][s]=0
dsum=0
for k in range(1,n+1):
    dsum=dsum+dp[n][k][k*a]
print(dsum)
    

### FIXED CODE ###

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

for i in range(n):
    x[i]=x[i]-a
    
nx=n*n
dp=[[0]*(2*nx+1) for i in range(n+1)]

#print(dp)

dp[0][nx]=1

for j in range(1,n+1):
    jj=j-1
    for t in range(2*nx+1):
        if t-x[jj]<0 or 2*nx<t-x[jj]:
            dp[j][t]=dp[j-1][t]
        elif 0<t-x[jj] and  t-x[jj]<2*nx:
            dp[j][t]=dp[j-1][t]+dp[j-1][t-x[jj]]
        else:
            dp[j][t]=0

print(dp[n][nx]-1)
### BUGGY CODE ###

def run():
  N, K = map(int, input().split())
  h_li = [int(h) for h in input().split()]
  cost_li = [0] * (N)
  cost_li[1] = abs(h_li[0] - h_li[1])
  for n in range(2, N):
    if n < K: k = n
    else: k = K
    cost = float('inf')
    h = h_li[n]
    for _k in range(1, k+1):
      cost = min(cost, cost_li[n-_k] + abs(h_li[n-_k]-h))
    cost_li[n] = cost
  print(cost_li[N-1])
  
if __name__ == '__main__':
  run()

### FIXED CODE ###

def run():
  N, K = map(int, input().split())
  h_li = [int(h) for h in input().split()]
  cost_li = [0] * (N)
  cost_li[1] = abs(h_li[0] - h_li[1])
  for n in range(2, N):
    if n < K: k = n
    else: k = K
    cost = float('inf')
    h = h_li[n]
    for _k in range(1, k+1):
      cost = min(cost, cost_li[n-_k] + abs(h_li[n-_k]-h))
    cost_li[n] = cost
  print(cost_li[N-1])
  
if __name__ == '__main__':
  run()
### BUGGY CODE ###

x=int(input())
for i in range(1,int(x**(1/2))+1):
    if x%i:continue

    ar,s=i,x//i
    pre=[]
    if (ar**5)%5==x%5:pre.append(ar)
    if  ((s**5)%5==x%5):pre.append(s)

    for a in set(pre):
        d=(x-a**5)//5//a
        if d==0:print(a,0);exit()
        for b in range(1,int(abs(d)**(1/2))+1):
            if d%b:continue
            if a**3+2*b*a**2+2*b**2*a+b**3==d//b:
                print(a+b,b);exit()
            if a**3-2*b*a**2+2*b**2*a-b**3==-(d//b):print(a-b,-b);exit()


### FIXED CODE ###

x=int(input())
for i in range(-120,121):
  for j in range(-120,121):
    if pow(i,5)-pow(j,5)==x:
      print(i,j);exit()
### BUGGY CODE ###

import collections
n,k = (int(i) for i in input().split())
a = list(int(i) for i in input().split())
c = collections.Counter(a)
ct = 0
for i in range(k):
 try:
  ct += c.most_common()[i][1]
 except:
  break
ans = n-ct
if ans <0:
  ans = 0
print(ans)

### FIXED CODE ###

import collections
n,k = (int(i) for i in input().split())
a = list(int(i) for i in input().split())
c = collections.Counter(a)
values,counts = zip(*c.most_common())
if len(counts) >= k:
 ans = sum(counts[k:])
else:
 ans = 0

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

from sys import stdin
s = str(stdin.readline().rstrip())
q = int(stdin.readline().rstrip())
for i in range(q):
    query = list(map(str, stdin.readline().rstrip().split()))
    if int(query[0])==1:
        s = s[::-1]
    else:
        if int(query[1])==2:
            s += query[2]
        else:
            s = query[2] + s

print(s)


### FIXED CODE ###

from sys import stdin
s = str(stdin.readline().rstrip())
#A, B, C = map(int, stdin.readline().rstrip().split())
#S = [list(map(int, stdin.readline().rstrip().split())) for _ in range(h)]#hの定義を忘れずに
q= int(stdin.readline().rstrip())
hanten = 0
t=""
u=""

for i in range(q):
    l = list(map(str, stdin.readline().rstrip().split()))
    if int(l[0]) == 1:
        t,u = u,t
        hanten ^= 1
    else:
        if int(l[1])==1:
            t+=l[2]
        else:
            u+=l[2]


if hanten==0:
    print(t[::-1]+s+u)
else:
    print(t[::-1]+s[::-1]+u)
### BUGGY CODE ###

n,k=map(int,input().split())
L=list(map(int,input().split()))
L.insert(0,0)
#print(L)
prev=L[1]
for i in range(1,k):
	nex = L[prev]
	prev = nex
print(nex)


### FIXED CODE ###

#very important question
n,k=map(int,input().split())
L=list(map(int,input().split()))

visit=[False]*(n+1)

town=[]

next=1
while 1:
    next = L[next-1]
    if not visit[next]:
        town.append(next)
        visit[next] = True
    else:
        town.append(next)
        break
#print(town)
for i in range(n):
    if town[i]==town[-1]:
        mod=i
        index=i
        loop=len(town)-i-1
        loop_array = town[i:-1]
        break

fin_len = (k-mod)%loop
if k<=mod:
    print(town[k-1])
else:
    print(loop_array[fin_len-1])
### BUGGY CODE ###

n = int(input())
path = []

for i in range(n):
    x,y = map(int,input().split())
    path.append((x,y,i))

x_li = sorted(path)
y_li = sorted(path,key=lambda x:(x[1]))

inf = 10**18
cost = [[inf for i in range(n)]for j in range(n)]

for i in range(1,n):
    cost[x_li[i][2]][x_li[i-1][2]] = min(abs(x_li[i][0]-x_li[i-1][0]),abs(x_li[i][1]-x_li[i-1][1]))
    cost[x_li[i-1][2]][x_li[i][2]] = min(abs(x_li[i][0]-x_li[i-1][0]),abs(x_li[i][1]-x_li[i-1][1]))
    cost[y_li[i][2]][y_li[i-1][2]] = min(abs(y_li[i][0]-y_li[i-1][0]),abs(y_li[i][1]-y_li[i-1][1]))
    cost[y_li[i-1][2]][y_li[i][2]] = min(abs(y_li[i][0]-y_li[i-1][0]),abs(y_li[i][1]-y_li[i-1][1]))

def prim(n,cost):
    mincost = [float("inf")]*n
    used = [False] * n
    mincost[0] = 0
    res = 0   
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1 or mincost[i] < mincost[v]):
                v = i
        if v == -1:
            break
        used[v] = True
        res += mincost[v]
        for i in range(n):
            mincost[i] = min(mincost[i],cost[v][i])
    return res

print(prim(n,cost))

### FIXED CODE ###

n = int(input())
path = []

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

for i in range(n):
    x,y = map(int,input().split())
    path.append((x,y,i))

x_li = sorted(path)
y_li = sorted(path,key=lambda x:(x[1]))

edge = []

for i in range(1,n):
    edge.append((x_li[i][2],x_li[i-1][2],x_li[i][0]-x_li[i-1][0]))
    edge.append((y_li[i][2],y_li[i-1][2],y_li[i][1]-y_li[i-1][1]))

edge.sort(key=lambda x:(x[2]))

uf = UnionFind(n)
cost = 0

for i,j,k in edge:
    if not uf.same(i,j):
        uf.union(i,j)
        cost += k

print(cost)
### BUGGY CODE ###

m, n = map(int, input().split())
mod = 1000000007
print(((m % mod) ** (n % mod)) % mod)



### FIXED CODE ###

m, n = map(int, input().split())
print(pow(m, n, 1000000007))
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))

ans = 1
for i in A_list:
    ans *= i
    if 1000000000000000000 < ans and 0 not in set(A_list):
        print('-1')
        exit()
    elif ans == 0:
        print(0)
        exit()
else:
    print(ans)


### FIXED CODE ###

def main():
    N = int(input())
    A_list = list(map(int, input().split()))

    if 0 in set(A_list):
        print(0)
        exit()

    ans = 1
    for i in A_list:
        ans *= i
        if 1000000000000000000 < ans:
            print('-1')
            exit()
    else:
        print(ans)


main()
### BUGGY CODE ###


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

mod = 10**9+7

def comb(n,r):
	u = 1
	d = 1
	for i in range(n-r+1,n+1):
		u *= i%mod

	for i in range(1,r+1):
		d *= i%mod
	D = pow(d,mod-2,mod)

	return u*D%mod

ans = pow(2,n,mod)-1-comb(n,a)-comb(n,b)

print(ans%mod)

### FIXED CODE ###

import itertools
import math
n,a,b = map(int,input().split())

mod = 10**9+7

def comb(n, r):
    ans = 1
    for i in range(r):
        ans = ans * (n-i) * pow(i+1, mod-2, mod) % mod
    return ans

print((pow(2, n, mod)-1-comb(n,a)-comb(n,b)) % mod)
### BUGGY CODE ###

import itertools
p = 998244353
q = 75497471

N,S = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
L = []
for i in range(1,N+1):
  for a in itertools.combinations(range(N),i):
    num = 0
    for j in a:
      num += A[j]
    if num == S:
      L.append(i)
ans = 0
for l in L:
  l = N-l
  t = l//30
  u = l%30
  num = 1
  for _ in range(t):
    num *= q
    num %= p
  num *= 2**u
  num %= p
  ans += num
  
print(ans)

### FIXED CODE ###

import numpy as np
p = 998244353

N,S = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
dp = np.zeros(S+1)
dp[0] = 1
for a in A:
  if S < a:
    dp *= 2
    dp %= p
    continue
  tmp = 2*dp
  dp = np.append(np.zeros(a),dp[:S-a+1])
  dp += tmp
  dp %= p
print(int(dp[S]))
### BUGGY CODE ###

from heapq import *
def dijkstra(s, n, w, cost):
    # s:始点,n:頂点数,w:辺の数,cost:辺ijの重み
    ans = [float('inf')] * n  # 最短距離の記録
    d = [[float('inf'), i] for i in range(n)]
    used = [False] * n  # 一度最短距離を確定した頂点はもう見ない
    ans[s] = 0
    d[s][0] = 0
    heapify(d)

    while d:
        D, V = heappop(d)
        if used[V]: continue
        used[V] = True

        for t, distance in cost[V]:
            ans[t] = min(ans[t], D + distance)
            heappush(d, [ans[t], t])
    return ans

n = int(input())
route_list = [[] for i in range(n)]  # 辺の移動の際のコスト
for i in range(n - 1):
    s, t, d = map(int, input().split())
    route_list[s - 1].append((t - 1, d))
    route_list[t - 1].append((s - 1, d))
# print(route_list)
q, k = map(int,input().split())

stand = dijkstra(k - 1, n, n - 1, route_list)
#print(stand)

for i in range(q):
    x, y = map(int,input().split())
    temp = stand[x - 1] + stand[y - 1]
    print(temp)

### FIXED CODE ###

#BFS
from collections import deque
def bfs(G):
    q=deque()
    q.append((k - 1, -1, 0))

    while q:
        #qの先頭を取り出す
        V, P, C = q.popleft()
        for new, cost in G[V]:
            if new == P:continue
            temp = C + cost
            q.append((new, V, temp))
            stand[new] = temp

n = int(input())
route_list = [[] for i in range(n)]  # 辺の移動の際のコスト
for i in range(n - 1):
    s, t, d = map(int, input().split())
    route_list[s - 1].append((t - 1, d))
    route_list[t - 1].append((s - 1, d))
# print(route_list)
q, k = map(int,input().split())


stand = [0] * n
bfs(route_list)
for i in range(q):
    x, y = map(int,input().split())
    temp = stand[x - 1] + stand[y - 1]
    print(temp)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq
from collections import deque
input = lambda: sys.stdin.buffer.readline()[:-1].decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
# heapq.heapify(hq)
ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)

    
    


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq
from collections import deque
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
# heapq.heapify(hq)
ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)
### BUGGY CODE ###

n=int(input())
ansl=[]
for i in range(n):
  tmp=input().rstrip()
  if not(tmp in ansl):
    ansl.append(tmp)
print(len(ansl))

### FIXED CODE ###

n=int(input())
ansl=[]
for i in range(n):
  ansl.append(input().rstrip())
print(len(set(ansl)))
### BUGGY CODE ###

a,b,c,k = map(int, input().split())
ans = 0
l = [a,b,c]
while k>0:
    if k < a:
        ans=k
        break
    else:
        ans += a 
        k-=a  
        a-=a 
    if k > b:
        k-=b
        b-=b
    else:
        k-=k
        b-=k    
    if k ==0:
        break    
    if k < c:
        ans += -k 
        k-=k
        break
    
print(ans)

### FIXED CODE ###

a,b,c,k = map(int, input().split())
ans = 0
l = [a,b,c]
while k>0:
    if k < a:
        ans=k
        break
    else:
        ans += a 
        k-=a  
        a-=a 
    if k ==0:
        break    
    if k > b:
        k-=b
        b-=b
    else:
        k-=k
        b-=k    
    if k ==0:
        break    
    if k < c:
        ans += -k 
        k-=k
    else:
        ans += -c
        k -= c
    if k ==0:
        break 
print(ans)
### BUGGY CODE ###

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

x = N
while x > abs(x-K):
    x = abs(x-K)

print(x)

### FIXED CODE ###

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

x = abs(N -(N//K)*K)
y = abs(N - (N//K + 1)*K)

if x < y:
    print(x)
else:
    print(y)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int, input().split())
    x,y = [], []
    for _ in range(m):
        a,b = map(int, input().split())
        if a==1:
            x.append(b)
        if b==n:
            y.append(a)
    for i in x:
        if i in y:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int, input().split())
    x,y = [], []
    for _ in range(m):
        a,b = map(int, input().split())
        if a==1:
            x.append(b)
        if b==n:
            y.append(a)
    if not len(x)+len(y)==len(set(x+y)):
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


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

# どちらか必ずa_Nのカードを持つ
import sys
from functools import lru_cache

sys.setrecursionlimit(4000)

N,Z,W = map(int,input().split())
A = list(map(int,input().split()))
A.reverse()

# turn: true->X, false->Y

@lru_cache(maxsize=4000000)
def rec(i,x,y,turn):
  if i == 0:
    return abs(x-y)
  if turn:
    return max(rec(j,A[j],y,False) for j in range(i))
  else:
    return min(rec(j,x,A[j],True) for j in range(i))

print(rec(N,Z,W,True))

### FIXED CODE ###

# どちらか必ずa_Nのカードを持つ

N,Z,W = map(int,input().split())
A = list(map(int,input().split()))
A.reverse()
A.append(W)

BOTTOM = A[0]

M = float('inf')
m = 0

for a in A[1:]:
  x = abs(BOTTOM-a)
  t = max(x,m)
  s = min(x,M)
  M = min(M,t)
  m = max(m,s)

print(t)
### BUGGY CODE ###

c = 0
k, s = map(int, input().split())

for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l == s:
                c += 1
print(c)

### FIXED CODE ###

c = 0
k, s = map(int, input().split())

for i in range(k+1):
    for j in range(k+1):
        if 0 <= s - i - j <= k:
            c += 1
print(c)
### BUGGY CODE ###

A,B,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
li2=[input() for i in range(m)]
c = []
for i in range(m):
    c.append( [int(x.strip()) for x in li2[i].split()])

ans = 10**6

for i in range(len(a)):
    for j in range(len(b)):
        keep = a[i]+b[j]
        coopon = 0
        for k in range(m):
            if c[k][0]-1 == i and c[k][1]-1 == j and coopon<c[k][2]:

                coopon = c[k][2]

        keep -= coopon

        if keep < ans:
            ans = keep

print(ans)

### FIXED CODE ###

A,B,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
li2=[input() for i in range(m)]
c = []
for i in range(m):
    c.append( [int(x.strip()) for x in li2[i].split()])

ans = min(a) + min (b)

for i in range(m):
    keep = a[c[i][0]-1] + b[c[i][1]-1] - c[i][2]
    if keep < ans:
        ans = keep

print(ans)