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

a, b, c, k = map(int, input().split())

ans = 0
for i in range(k):
    if a > 0:
        ans += 1
        a -= 1

    elif b > 0:
        b -= 1

    elif c > 0:
        ans -= 1
        c -= 1

print(ans)


### FIXED CODE ###

a, b, c, k = map(int, input().split())

ans = 0
if a < k:
    ans = a
else:
    ans = k

minus = k - (a + b)

if minus > 0:
    ans -= minus

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

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N + 200 : break
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N, M = map(int, input().split())
L, R = [0]*M, [0]*M
for i in range(M):
    L[i],R[i] = map(int, input().split())

cnt = 0
LR = zip(L,R)
res = set(range(1,N+1))
for l,r in LR:
    res &= set(range(l,r+1))
print(len(res))

### FIXED CODE ###

N, M = map(int, input().split())
L, R = [0]*M, [0]*M
for i in range(M):
    L[i],R[i] = map(int, input().split())

a, b = max(L), min(R)
if a<=b:
    print(b-a+1)
else:
    print(0)
### BUGGY CODE ###

N = int(input())
s = []
for i in range(N):
    s.append(sorted(input()))

cnt = 0
for i in range(N-1):
    for j in range(i+1, N):
        if (s[i] == s[j]):
            cnt += 1

print(cnt)


### FIXED CODE ###

from collections import defaultdict
N = int(input())
s = [''.join(sorted(input())) for i in range(N)]
d = defaultdict(lambda: 0)

for _s in s:
    d[_s] += 1

print(sum(map(lambda x: x * (x-1) // 2, d.values())))
### BUGGY CODE ###

import numpy as np
x,y,z,k = map(int,input().split())
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))
ans = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            ans.append(a[i] + b[j] + c[l])
ans.sort(reverse = True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = []
for i in range(x):
    for j in range(y):
        ans.append(a[i]+b[j])
ans.sort(reverse=True)
ans = ans[:k]
ans2 = []
for i in range(len(ans)):
    for j in range(z):
        ans2.append(ans[i]+c[j])
ans2.sort(reverse=True)
for i in range(k):
    print(ans2[i])
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

t = 0
ans = 0

for i in range(n):
  t = sum(a[:i+1])
  if t <= k and i + 1 > ans:
      ans = i + 1
  elif t > k:
    break

  for j in range(m):
    t = sum(a[:i+1]) + sum(b[:j+1])
    if t <= k and i + j + 2> ans:
      ans = i + j + 2
    elif t > k:
      break

print(ans)




### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
s = list(input())

seq = []

if s[0] == '1':
    seq.append(0)

prev = s[0]
seq_val = 1
for i in range(1, n):
    if s[i] == prev:
        seq_val += 1
    else:
        seq.append(seq_val)
        seq_val = 1
        prev = s[i]

seq += [n-sum(seq)]

ans = 0
for i in range(n):
    if i % 2 == 0:
        # print(seq[i:i+2*k])
        ans = max(ans, sum(seq[i:i+2*k]))
    else:
        # print(seq[i:i+2*k])
        ans = max(ans, sum(seq[i:i+2*k+1]))

print(ans)

### FIXED CODE ###

import itertools

n, k = map(int,input().split())
s = input()
seq = []

if s[0] == '0':
    seq.append(0)

i = 1
seq_cnt = 1
while i != n:
    if s[i] != s[i-1]:
        seq.append(seq_cnt)
        seq_cnt = 1
    else:
        seq_cnt += 1
    i += 1

seq.append(seq_cnt)
if s[-1] == '0':
    seq.append(0)

b = [0] + list(itertools.accumulate(seq))

ans = 0
for left in range(0, len(b), 2):
    right = left + 2*k + 1
    if right >= len(b):
        right = len(b)-1

    ans = max(ans, b[right] - b[left])

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

s = input()
lst = []
for i in range(len(s)):
  n = int(s[i::])
  lst.append(n%2019)
lst.append(0)
lst.sort()
counter = 1
stock = lst[0]
ans = 0
for i in range(1, len(lst)):
  if stock == lst[i]:
    counter += 1
  else:
    ans += counter*(counter - 1)//2
    counter = 1
    stock = lst[i]
if counter >= 2:
  ans += counter*(counter - 1)//2
print(ans)
  

### FIXED CODE ###

import collections
MOD = 2019

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)

s = input()
lst = []
n = 0
for i in range(len(s)):
  n += mod(int(s[len(s)-i-1])*modpow(10, i))
  lst.append(mod(n))
lst.append(0)
lst.sort()
ans = 0
counter = 1
stock = lst[0]
for i in range(1, len(lst)):
  if stock == lst[i]:
    counter += 1
  else:
    ans += counter*(counter - 1)//2
    counter = 1
    stock = lst[i]
if counter >= 2:
  ans += counter*(counter - 1)//2
print(ans)
### BUGGY CODE ###

def main():
    import sys
    from itertools import accumulate
    input=sys.stdin.buffer.readline
    n,k=map(int,input().split())
    *a,=map(int,input().split())
    for _ in range(k):
        b=[0]*n
        for i,t in enumerate(a):
            if(j:=i-t)<0:j=0
            b[j]+=1
            if(j:=i-~t)<n:b[j]-=1
        *a,=accumulate(b)
        if min(a)==n:break
    print(' '.join(map(str,a)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappop, heappush
import sys
def main(X, Y, Z, K, A, B, C):
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    used = [[[False] * Z for _ in range(Y)] for __ in range(X)]
    q = [(-(A[0] + B[0] + C[0]), 0, 0, 0)]
    used[0][0][0] = True
    for i in range(K):
        v, ai, bi, ci = heappop(q)
        print(-v)
        for nai, nbi, nci in [(ai + 1, bi, ci), (ai, bi + 1, ci), (ai, bi, ci + 1)]:
            if nai >= X or nbi >= Y or nci >= Z: continue
            if used[nai][nbi][nci]: continue
            used[nai][nbi][nci] = True
            heappush(q, (-(A[nai] + B[nbi] + C[nci]), nai, nbi, nci))

if __name__ == '__main__':
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    *C, = map(int, input().split())
    main(X, Y, Z, K, A, B, C)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import product
import sys
def main(X, Y, Z, K, A, B, C):
    AB = sorted([a + b for a, b in product(A, B)], reverse=True)
    ABC = sorted([ab + c for ab, c in product(AB[:K], C)], reverse=True)
    for k in range(K):
        print(ABC[k])

if __name__ == '__main__':
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    *C, = map(int, input().split())
    main(X, Y, Z, K, A, B, C)
### BUGGY CODE ###

s = input()
t = input()

ls = len(s)
lt = len(t)
ans = ""
dp = [[0]*(ls+1) for i in range(lt+1)]
memo = [[""]*(ls+1) for i in range(lt+1)]

for i in range(1,lt+1):
    for j in range(1,ls+1):
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        memo[i][j] = memo[i-1][j-1]
        if s[j-1] == t[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            memo[i][j] = memo[i-1][j-1]+s[j-1]

i = lt
j = ls
while i-1>=0 and j-1>=0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    else:

        i -= 1
        j -= 1
        ans = s[j] + ans

print(ans)



### FIXED CODE ###

s = input()
t = input()
N = len(s)
M = len(t)

dp = [[0]*(N+1) for i in range(M+1)]

for i in range(1,M+1):
  for j in range(1,N+1):
    if s[j-1] == t[i-1]:
      dp[i][j] = dp[i-1][j-1]+1
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])
L = dp[-1][-1]
i = M
j = N
ans = [""]*L
cur = L-1
while i>=0 and j>=0:
  if dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1]:
    ans[cur] = s[j-1]
    i -= 1
    j -= 1
    cur -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    j -= 1
print("".join(ans))
### BUGGY CODE ###

N, K = map(int, input().split())
hList = list(map(int, input().split()))
ans = 0
dp = [0] * N
dp[0] = 0

for i in range(1, N):
    minT = 1000000000
    for j in range(i - 1, i - K - 1, -1):
        tmp = dp[j] + abs(hList[j] - hList[i])
        minT = min(minT, tmp)
        if j == 0:
            break
    dp[i] = minT

print(dp[N - 1])

### FIXED CODE ###

N, K = map(int, input().split())
hList = list(map(int, input().split()))
ans = 0
dp = [0] * N
dp[0] = 0

for i in range(1, N):
    minT = 1000000000
    for j in range(i - 1, i - K - 1, -1):
        tmp = dp[j] + abs(hList[j] - hList[i])
        minT = min(minT, tmp)
        if j == 0:
            break
    dp[i] = minT

print(dp[N - 1])
### BUGGY CODE ###

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

    count = 1
    for i in range(1,N):
        if sum([1 for x in P[:i] if x<P[i]])>=1:
            continue
        else:
            count += 1
    print(count)
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    P = list(map(int,input().split()))
    min_val = 2*10e5
    count = 1
    for i in range(1,N):
        if min_val > P[i-1]:
            min_val = P[i-1]
        if P[i] <= min_val:
            count += 1
    print(count)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

total = sum(A)
each = N*(N+1) // 2
if total % each != 0:
    NO()
    exit()
cnt = total // each

for i in range(cnt):
    idx = A.index(min(A))
    for j in range(idx, idx+N):
        sub = j - idx + 1
        j %= N
        A[j] -= sub
if all(a == 0 for a in A):
    YES()
else:
    NO()


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

total = sum(A)
each = N*(N+1) // 2
if total % each != 0:
    NO()
    exit()
# 操作回数
K = total // each

# A各値の差分で数列Bを作る
B = [0] * N
for i in range(N):
    j = (i+1) % N
    B[i] = A[j] - A[i]
# ここからK引けば、1度の操作につきBのいずれかの要素を+N、とできる
B = [b-K for b in B]

if all(b % N == 0 and b <= 0 for b in B):
    YES()
else:
    NO()
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
pq = []
for i, b in enumerate(B):
    if A[i] != b:
        heappush(pq, (-b, i))
ans = 0
while pq:
    _, i = heappop(pq)
    B[i] -= B[(i-1) % N] + B[(i+1) % N]
    if B[i] < A[i]:
        ans = -1
        break
    if B[i] > A[i]:
        heappush(pq, (-B[i], i))
    ans += 1
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
pq = []
for i, b in enumerate(B):
    if A[i] != b:
        heappush(pq, (-b, i))
ans = 0
while pq:
    _, i = heappop(pq)
    s = B[(i-1) % N] + B[(i+1) % N]
    q, r = divmod(B[i] - A[i], s)
    B[i] = A[i] + r
    ans += q
    if q == 0:
        ans = -1
        break
    if B[i] > A[i]:
        heappush(pq, (-B[i], i))
print(ans)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]
c = 0
while S != []:
  s = S.pop(0)
  if s in S:
    continue
  else:
    c += 1
print(c)

### FIXED CODE ###

N = int(input())
S = {input() for _ in range(N)}
print(len(S))
### BUGGY CODE ###

import numpy as np
from numba import njit

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

@njit
def light(a_list):
    outcome= np.array([0]*(n+1))
    for i in range(n):
        outcome[max(0,i-a_list[i])] += 1
        outcome[min(n,i+a_list[i]+1)] -= 1
    outcome = np.cumsum(outcome)[:-1]
    return outcome

for _ in range(k):
    if sum(a) >= n*n:
        break
    a = light(a)

[print(aa,end=' ') for aa in a]

### FIXED CODE ###

import numpy as np
from numba import njit

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

@njit(cache=True)
def light(n,a_list):
    outcome= np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        outcome[max(0,i-a_list[i])] += 1
        outcome[min(n,i+a_list[i]+1)] -= 1
    outcome = np.cumsum(outcome)[:-1]
    return outcome

for _ in range(k):
    if min(a) == n:
        break
    a = light(n,a)

[print(aa,end=' ') for aa in a]
### BUGGY CODE ###


N = int(input())
def luca(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return luca(n-1)+luca(n-2)
print(luca(N))

### FIXED CODE ###

from functools import lru_cache
N = int(input())
@lru_cache(maxsize=1000)
def luca(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return luca(n-1)+luca(n-2)
print(luca(N))
### BUGGY CODE ###

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

import numpy as np
p=np.zeros(N).astype(int)+K

for i in range(Q):
  j=int(input())-1
  p[j]=p[j]+1
  p=p-1
  
for i in range(N):
  if p[i]<1:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

p=[-Q]*N

for i in range(Q):
  j=int(input())-1
  p[j]=p[j]+1

for i in range(N):
  if p[i]+K<1:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)

N, Q = [int(x) for x in input().split()]

V = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    V[a].add(b)

C = [0] * N

for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    C[p] += x

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


def main():
    dfs(0, 0)
    print(" ".join([str(x) for x in ANS]))

if __name__ == '__main__':
   main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10000000)

N, Q = [int(x) for x in input().split()]
# V = [set() for _ in range(N)]
V = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    # V[a].add(b)
    V[a].append(b)

C = [0] * N

for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    C[p] += x

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


def main():
    dfs(0, 0)
    print(" ".join([str(x) for x in ANS]))


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

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

for i in range(n - k + 1):
    ans = max(ans, sum(p[i:i+k]))
    
print(0.5 * (ans + k))


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
s = [0 for _ in range(n + 1)]
ans = 0
for i in range(n):
    s[i+1] = p[i] + s[i]

for i in range(n - k + 1):
    ans = max(ans, s[i + k] - s[i])

print((ans + k) * 0.5)
### BUGGY CODE ###

from collections import deque, Counter
import sys
H, W = map(int, input().split())
count = 0
grid = ['s' for h in range(H)]
for h in range(H):
    grid[h] = list(input())
    tmp_count = Counter(grid[h])['#']
    if tmp_count == W:
        print(-1)
        sys.exit()
    count += tmp_count

deq = deque([(0, 0)])
visited = [[False for w in range(W)] for h in range(H)]
visited[0][0] = True
route = 0
while deq:
    route += 1
    for _ in range(len(deq)):
        coord = deq.popleft()
        h, w = coord
        visited[h][w] = True
        if coord == (H - 1, W - 1):
            print(H * W - route - count)
            sys.exit()
        if h < H - 1:
            if grid[h + 1][w] != '#' and not visited[h + 1][w]:
                deq.append((h + 1, w))
        if w < W - 1:
            if grid[h][w + 1] != '#' and not visited[h][w + 1]:
                deq.append((h, w + 1))
        if h > 0:
            if grid[h - 1][w] != '#' and not visited[h - 1][w]:
                deq.append((h - 1, w))
        if w > 0:
            if grid[h][w - 1] != '#' and not visited[h][w - 1]:
                deq.append((h, w - 1))

print(-1)




### FIXED CODE ###

from collections import deque, Counter
import sys
H, W = map(int, input().split())
count = 0
grid = ['s' for h in range(H)]
for h in range(H):
    grid[h] = list(input())
    tmp_count = Counter(grid[h])['#']
    if tmp_count == W:
        print(-1)
        sys.exit()
    count += tmp_count

deq = deque([(0, 0)])
visited = [[-1 for w in range(W)] for h in range(H)]
visited[0][0] = 0
route = 0
while deq:
    for _ in range(len(deq)):
        h, w = deq.popleft()
        #print(h, w)
        if (h, w) == (H - 1, W - 1):
            print(H * W - visited[h][w] - 1 - count)
            sys.exit()
        for j, k in ([-1, 0], [0, -1], [0, 1], [1, 0]):
            new_h, new_w = h + j, w + k
            if 0 <= new_h <= H - 1 and 0 <= new_w <= W - 1:
                if grid[new_h][new_w] != '#' and visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    deq.append((new_h, new_w))
print(-1)
### BUGGY CODE ###

N = int(input())
ans = 1
for i in range(1, N+1):
    ans *= i
print(ans % (10**9 + 7))

### FIXED CODE ###

N = int(input())
ans = 1
for i in range(1, N+1):
    ans =ans * i % (10**9 + 7)
print(ans)
### BUGGY CODE ###

N,M =map(int,input().split())
p = list(map(lambda x:int(x)-1,input().split()))
xy = [list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
group = [i for i in range(N)]
glist = [[i] for i in range(N)]
def merge(x,y):
    gx = group[x]
    gy = group[y]
    if gx == gy:
        return
    for y in glist[gy]:
        group[y] = gx
    glist[gx] += glist[gy]
    glist[gy] = []
    return
for x,y in xy:
    merge(x,y)
out = sum([len(set(row) & set(p[g] for g in row)) for row in glist])
print(out)

### FIXED CODE ###

N,M =map(int,input().split())
p = list(map(lambda x:int(x)-1,input().split()))
xy = [list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
group = [i for i in range(N)]
glist = [[i] for i in range(N)]
def merge(x,y):
    gx = group[x]
    gy = group[y]
    if gx == gy:
        return
    if len(glist[gx])<len(glist[gy]):
        gx,gy = gy,gx
    for y in glist[gy]:
        group[y] = gx
    glist[gx] += glist[gy]
    glist[gy] = []
    return
for x,y in xy:
    merge(x,y)
out = sum([len(set(row) & set(p[g] for g in row)) for row in glist])
print(out)
### BUGGY CODE ###

H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
b = []

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b.append((tmp[0], tmp[1]))

t = max(hallline)
s = max(wallline)

a = [i for i in range(H) if hallline[i] == t]
c = [i for i in range(W) if wallline[i] == s]

for i in a:
    for j in c:
        if (i, j) not in b:
            print(t + s)
            exit()
print(t + s - 1)


### FIXED CODE ###

H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
b = {}

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[(tmp[0], tmp[1])] = True

t = max(hallline)
s = max(wallline)

a = [i for i in range(H) if hallline[i] == t]
c = [i for i in range(W) if wallline[i] == s]

tmp = False

for i in a:
    for j in c:
        if (i, j) not in b.keys():
            print(t + s)
            tmp = True
            break
    if tmp:
        break
if not tmp:
    print(t + s - 1)
### BUGGY CODE ###

import sys
import heapq as h
stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def dist(p,q):
  px,py,pr = p
  qx,qy,qr = q
  d = ((px-qx)**2 + (py-qy)**2)**.5
  return max(d-(pr+qr),0)
  
  

xs,ys,xt,yt = nm()
n = ni()
pl = [(xs,ys,0)] + [tuple(nm()) for _ in range(n)] + [(xt,yt,0)]
gr = [dict() for _ in range(n+2)]
for i in range(n+1):
  for j in range(i+1,n+2):
    gr[i][j] = dist(pl[i],pl[j])
    gr[j][i] = gr[i][j]

dis = [float("inf")]*(n+2)
q = [(0,0)]
while q:
  d,v = h.heappop(q)
  if dis[v] <= d:
    continue
  dis[v] = d
  for x in gr[v]:
    if dis[x] > dis[v]+gr[v][x]:
      h.heappush(q,(dis[v]+gr[v][x],x))
print(dis[-1])

### FIXED CODE ###

import sys
import heapq as h
stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def dist(p,q):
  px,py,pr = p
  qx,qy,qr = q
  d = ((px-qx)**2 + (py-qy)**2)**.5
  return max(d-(pr+qr),0)
  
  

xs,ys,xt,yt = nm()
n = ni()
pl = [(xs,ys,0)] + [tuple(nm()) for _ in range(n)] + [(xt,yt,0)]
gr = [dict() for _ in range(n+2)]
for i in range(n+1):
  for j in range(i+1,n+2):
    gr[i][j] = dist(pl[i],pl[j])
    gr[j][i] = gr[i][j]

dis = [float("inf")]*(n+2)
q = [(0,0)]
while q:
  d,v = h.heappop(q)
  if dis[v] <= d:
    continue
  dis[v] = d
  for x in gr[v]:
    if dis[x] > dis[v]+gr[v][x]:
      h.heappush(q,(dis[v]+gr[v][x],x))
print(dis[-1])