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

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

### FIXED CODE ###

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

ans.append(min(rei)+min(den))
print(min(ans))
### BUGGY CODE ###

s = input()
x, y = map(int, input().split())
x += 8500
y += 8500

dpx = [0 for i in range(17000)]
dpy = [0 for i in range(17000)]

dpx[8500] = 1
dpy[8500] = 1

f = s.split("T")

fx = []
fy = []

for i, fi in enumerate(f):
    if i % 2:
        fy.append(len(fi))
    else:
        fx.append(len(fi))

for i, fxi in enumerate(fx):
    nex = [0] * 17000
    for j in range(17000):
        if dpx[j]:
            if fxi + j < 17000:
                nex[fxi + j] = 1
            if i > 0 and j - fxi >= 0:
                nex[j - fxi] = 1
    dpx = nex
        
for fyi in fy:
    nex = [0] * 17000
    for j in range(17000):
        if dpy[j]:
            if fyi + j < 17000:
                nex[fyi + j] = 1
            if j - fyi >= 0:
                nex[j - fyi] = 1
    dpy = nex

if dpx[x] and dpy[y]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = input()
x, y = map(int, input().split())
x += 8500
y += 8500

dpx = [0 for i in range(17000)]
dpy = [0 for i in range(17000)]

dpx[8500] = 1
dpy[8500] = 1

f = s.split("T")

fx = []
fy = []

for i, fi in enumerate(f):
    if i % 2:
        fy.append(len(fi))
    else:
        fx.append(len(fi))

for i, fxi in enumerate(fx):
    nex = [0] * 17000
    for j in range(17000):
        if dpx[j]:
            if fxi + j < 17000:
                nex[fxi + j] = 1
            if i > 0 and j - fxi >= 0:
                nex[j - fxi] = 1
    dpx = nex[:]
        
for fyi in fy:
    nex = [0] * 17000
    for j in range(17000):
        if dpy[j]:
            if fyi + j < 17000:
                nex[fyi + j] = 1
            if j - fyi >= 0:
                nex[j - fyi] = 1
    dpy = nex[:]

if dpx[x] and dpy[y]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import sys

# import os
# path = os.getcwd()
# path = os.path.join(path,"input.txt")
# sys.stdin = open(path)

input = sys.stdin.readline
N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [float('inf')]*(K)
dp.append(0)
dp = dp[::-1]
for i in range(N-1):
    dp_ = dp.pop(0)
    if i >= N-K-1:
        dp = [min(dp_+abs(H[i+j+1]-H[i]),dp[j]) for j in range(N-i-1)]
        continue
    dp = [min(dp_+abs(H[i+j+1]-H[i]),dp[j])  for j in range(K)]
    dp.append(float("inf"))

print(dp[0])
        

### FIXED CODE ###

import sys

# import os
# path = os.getcwd()
# path = os.path.join(path,"input.txt")
# sys.stdin = open(path)

input = sys.stdin.readline
N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [float('inf')]*(K)
dp.append(0)
dp = dp[::-1]
for i in range(N-1):
    dp_ = dp.pop(0)
    if i >= N-K-1:
        dp = [min(dp_+abs(H[i+j+1]-H[i]),dp[j]) for j in range(N-i-1)]
        continue
    dp = [min(dp_+abs(H[i+j+1]-H[i]),dp[j])  for j in range(K)]
    dp.append(float("inf"))

print(dp[0])
### BUGGY CODE ###

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

# In[10]:


N,K = map(int,input().split())
new = abs(N-K)
while(new<N):
    N = new
    new = abs(new-K)
print(N)



### FIXED CODE ###

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

# In[10]:


N,K = map(int,input().split())
new = N % K
n2 = K - new

print(min(new,n2))
### BUGGY CODE ###

S = str(input())
ans = 0
for i in range(len(S)+1):
    for j in range(i+1,len(S)+1):
        if(int(S[i:j]) % 2019 == 0):
            ans += 1
print(ans)


### FIXED CODE ###

S = str(input())
# 余りのリスト
counts = [0] * 2019
n, d = 0, 1

for s in S[::-1]:
    n += int(s) * d
    d *= 10
    n %= 2019
    d %= 2019
    counts[n] += 1
ans = counts[0]
for count in counts:
    ans += count * (count - 1) // 2
print(ans)
### BUGGY CODE ###

def resolve():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k):
        nxt = [0]*n
        for j in range(len(a)):
            r = min(j + a[j], n-1) #look right
            l = max(j-a[j], 0) #look left
            for m in range(l, r+1):
                nxt[m] = min(nxt[m]+1,n)
        a, nxt = nxt, a
        if a == nxt:
            break
    print(*a)
resolve()

### FIXED CODE ###

def resolve():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k):
        nxt = [0]*n
        for j in range(len(a)):
            r = min(j + a[j], n-1) #look right
            l = max(j-a[j], 0) #look left
            nxt[l] += 1
            if r+1 < n:
                nxt[r+1] -= 1
        b = [0] *n
        for j in range(len(a)):
            if j== 0:
                b[j] = nxt[j]
            else:
                b[j] = (nxt[j]+b[j-1])
        a, b = b, a
        if a == b:
            break
    print(*a)
resolve()
### BUGGY CODE ###

n, m = map(int, input().split())
ab_list = list()
for _ in range(m):
    a, b = map(int, input().split())
    ab_list.append([a, b])
ab_list = sorted(ab_list, key=lambda x: x[1])
n_list = [1 for i in range(n)]
for a, b in ab_list:
    flag = False
    for i in range(a, b):
        if n_list[i] == 0:
            flag = True
            break
    if not flag:
        n_list[b-1] = 0
print(n_list.count(0))

### FIXED CODE ###

n, m = map(int, input().split())
ab_list = list()
for _ in range(m):
    a, b = map(int, input().split())
    ab_list.append([a, b])
ab_list = sorted(ab_list, key=lambda x: x[1])
x = -1
ans = 0
for a, b in ab_list:
    if a <= x:
        continue
    else:
        x = b-1
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def main():
    N = int(input())
    for i in range(int(N ** 0.5), N + 1):
        if N % i == 0:
            print(len(str(i)))
            break


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def main():
    N = int(input())
    for i in range(int(N ** 0.5), 0, -1):
        if N % i == 0:
            print(len(str(N // i)))
            break


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

n=int(input())
i=1
j=1
while j!=n+1:
    i=i*j
    j+=1
print(i%(10**9+7))

### FIXED CODE ###

n=int(input())
i=1
j=1
while j!=n+1:
    i=(i*j)%(10**9+7)
    j+=1
print(i)
### BUGGY CODE ###

n = int(input())
l = [int(i) for i in input().split()]
l.sort()
s = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if l[k] < l[i] + l[j]:
        s += 1
      else:
        break
print(s)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    ans += bisect_left(l, l[i]+l[j]) - j - 1
print(ans)
### BUGGY CODE ###

N = int(input())
*A, = map(int, input().split())
if 0 in A: print(0)
else:
    ans = 1
    for a in A:
        ans *= a
        if ans > 10**18: ans = -1
    print(ans)

### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())
if 0 in A: print(0)
else:
    ans = 1
    for a in A:
        ans *= a
        if ans > 10**18: ans = -1; break
    print(ans)
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += math.gcd(a,math.gcd(b,c))
      
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0

for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += gcd(a,gcd(b,c))
      
print(ans)
### BUGGY CODE ###

T = int(input())
ABCD = [list(map(int,input().split())) for _ in range(T)]

for a,b,c,d in ABCD:
    count = 0
    dp = [a]
    now = a
    for _ in range(c+2):
        if now < b:
            print('No')
            break
        now %= b
        if now in dp:
            print('Yes')
            break
        if now > c:
            print('No')
            break
        dp.append(now)
        now += d


### FIXED CODE ###

#from math import gcd
from fractions import gcd
T = int(input())
ABCD = [list(map(int,input().split())) for _ in range(T)]

for a,b,c,d in ABCD:
    if a < b:
        print('No')
        continue
    if d < b:
        print('No')
        continue
    tmp = a % b
    if tmp > c:
        print('No')
        continue
    if d % b == 0:
        print('Yes')
        continue
    if c >= b-1:
        print('Yes')
        continue
    if a%2 == 0 and b%2 == 0 and d %2 == 0 and b-c == 2:
        print('Yes')
        continue
    GCD = gcd(b,d)
    if b-GCD +(a%GCD) > c:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 1
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    t = max(t, res + 1)
  dp[v] = t
  return t

def toId(i, j, id):
  if i > j:
    i, j = j, i
  return id[i][j]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()


### FIXED CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()
### BUGGY CODE ###

n=int(input())
s=input()
r=[]
g=[]
b=[]
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    else:
        b.append(i)

ans=len(r)*len(g)*len(b)
for i in r:
    for j in g:
        for k in b:
            t=[i,j,k]
            t.sort()
            x,y,z=t
            if y-x == z-y:
                ans-=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in range(n):
    if s[i]=="R":
        r+=1
    elif s[i]=="G":
        g+=1
    else:
        b+=1
ans=r*g*b
sub=0
for i in range(n-2):
    for j in range(i+1,n-1):
        k=j+(j-i)
        if s[i]==s[j]:
            continue
        if k>=n or s[i]==s[k] or s[j]==s[k]:
            continue
        sub+=1
print(ans-sub)
### BUGGY CODE ###

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab = sorted(ab,key=lambda x: x[0],reverse=True)
b = [i[1] for i in ab]
b_set = list(set(b))
d = {}
for i in b_set:
    d[i] = []
for i in ab:
    d[i[1]].append(i[0])
dk = sorted(list(d.keys()),reverse=True)
ans = 0
for i in range(1,m+1):
    x = 0
    for j in dk:
        if d[j]:
            if d[j][-1] <= i:
                y = d[j].pop(-1)
                x = j
                break
    ans += x
print(ans)

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for i in range(n)]
ab = sorted(ab,key=lambda x: x[0],reverse=True)
heap = []
ans = 0
for i in range(1,m+1):
    while True:
        if not ab:
            break
        elif ab[-1][0] <= i:
            x = ab.pop(-1)
            heapq.heappush(heap,x[1]*-1)
        else:
            break
    if heap:
        y = heapq.heappop(heap)
        ans += y*-1
print(ans)
### BUGGY CODE ###

def f(h):
    #print(f"h = {h}")
    count = 0
    while len(h):
        n = h.count(1)
        if n:
            h.pop(h.index(1))
            count += 1
        if len(h) and h[0] > 1:
            new = h.pop(0) // 2
            h.append(new)
            h.append(new)
            count += 1
    return count

h = [int(input())]
print(f(h))



### FIXED CODE ###

def f(h):
    return 0 if h==0 else 1 + 2*f(int(h/2))

h = int(input())
print(f(h))
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    count = 0
    for i in range(n):
        for j in range(i+2,n,1):
            if a[i]+a[j]==abs(i-j): count+=1
    print(count)

main()


### FIXED CODE ###

from collections import Counter

def main():
    # n:人数, a:身長リスト
    n = int(input())
    a = list(map(int, input().split()))
    # Li=i+Ai, Ri=i-Aiを満たすL,Rを作成
    L = [0]*n
    R = [0]*n
    for i,ai in enumerate(a):
        L[i] = i+ai
        R[i] = i-ai
    # Li=X=Rj,i<jを満たす組が存在する時count+=1
    count = 0
    c = Counter(R)
    for Li in L:
        count += c.get(Li,0)

    print(count)

main()
### BUGGY CODE ###

N = int(input())
A, B = [], []
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
x, y = 0, 0
for i in range(N//2):
  if A.index(max(A)) == B.index(max(B)):
    s = A.index(max(A))
    x += A[s]
    A.pop(s)
    B.pop(s)
    t = B.index(max(B))
    y += B[t]
    A.pop(t)
    B.pop(t)
  else:
    s = max(A)
    t = max(B)
    u = A[B.index(t)]
    w = sorted(B)[-2]
    if s-t >= u-w:
      x += s
      y += t
    else:
      x += u
      y += w
      
if N % 2 == 1:
  x += A[0]
print(x-y)

### FIXED CODE ###

N = int(input())
A, B = [], []
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
l = []
for i in range(N):
  l.append(A[i]+B[i])
l.sort(reverse=True)

ans = 0
for i in range(N//2):
  ans += l[2*i]
if N % 2 == 1:
  ans += l[-1]
ans -= sum(B)
print(ans)
### BUGGY CODE ###

N,C = [int(i) for i in input().split()]
D = [[int(j) for j in input().split()] for i in range(C)]
c = [[int(j) for j in input().split()] for i in range(N)]
bank = [[],[],[]]
for i in range(N):
    for j in range(N):
        bank[(i+j)%3].append(c[i][j]-1)


min = 100000
for i in [ii for ii in range(C)]:
    for j in [jj for jj in range(C) if jj != i]:
        for k in [kk for kk in range(C) if kk != i and kk != j]:
            count = 0
            for x in bank[0]:
                if x != i:
                    count += D[x][i]
            for y in bank[1]:
                if y != j:
                    count += D[y][j]
            for z in bank[2]:
                if z != k:
                    count += D[z][k]
            if min > count:
                min = count
print(min)




### FIXED CODE ###

N,C = [int(i) for i in input().split()]
D = [[int(j) for j in input().split()] for i in range(C)]
c_temp = [[int(j)-1 for j in input().split()] for i in range(N)]
c = [[0 for i in range(C)] for j in range(3)]
for i in range(N):
    for j in range(N):
        c[(i+j)%3][c_temp[i][j]] += 1

min = 10**15
for i in [ii for ii in range(C)]:
    for j in [jj for jj in range(C) if jj != i]:
        for k in [kk for kk in range(C) if kk != i and kk != j]:
            count = sum([D[x][i]*c[0][x] + D[x][j]*c[1][x] + D[x][k]*c[2][x] for x in range(C)])
            if min > count:
                min = count
print(min)
### BUGGY CODE ###

A, B, N = map(int, input().split(' '))
ans = 0
for x in range(N + 1):
    if not x % B: continue
    res = ((A * (x % B)) - ((A * x) % B)) / B
    ans = max(ans, res)
print(int(ans))


### FIXED CODE ###

import math

A, B, N = map(int, input().split(' '))
ans = 0
x = min(B, N + 1) - 1
ans = math.floor((A * x) / B) - A * (math.floor(x / B))
print(int(ans))
### BUGGY CODE ###

def solve(string):
    n, m, q, *lrpq = map(int, string.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    ans = []
    for p, q in zip(pq[::2], pq[1::2]):
        ans.append(str(sum([1 if p <= l and r <= q else 0 for l, r in zip(lr[::2], lr[1::2])])))
    return "\n".join(ans)


if __name__ == '__main__':
    n, m, q = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))


### FIXED CODE ###

def solve(string):
    n, m, q, *lrpq = map(int, string.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    t = [[0] * (n + 1) for _ in range(n + 1)]
    for l, r in zip(lr[::2], lr[1::2]):
        t[l][r] += 1
    for i in range(n + 1):
        for j in range(n + 1):
            if j > 0:
                t[i][j] += t[i][j - 1]

    ans = [
        str(sum([t[i][q] - t[i][p - 1]
                 for i in range(p, q + 1)]))
        for p, q in zip(pq[::2], pq[1::2])
    ]
    return "\n".join(ans)


if __name__ == '__main__':
    n, m, q = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))
### BUGGY CODE ###

import math
n,m = map(int, input().split())
if m%n==0:
    print(m//n)
else:
    def make_divisor_list(num):
        if num < 1:
            return []
        elif num == 1:
            return [1]
        else:
            divisor_list = []
            divisor_list.append(1)
            for i in range(2, num // 2 + 1):
                if num % i == 0:
                    divisor_list.append(i)
            divisor_list.append(num)

            return divisor_list
    
    listD = make_divisor_list(m)
    index =0
    while index <len(listD):
        if listD[index]>n-1:
            print(m//listD[index])
            break
        index+=1


### FIXED CODE ###

import math
import time
n, m = map(int, input().split())
flag=0
if m%n==0:
    print(m//n)

else:
    start = time.time()
    index=m//n
    while index >0:
        elapsedTime = time.time()-start
        if elapsedTime > 1:
            flag=1
            break
        elif m%index==0:
            print(index)
            break
        index-=1

    if flag==1:
        index = 1
        while index < m+1:
            if m % index == 0:
                if index > n-1:
                    print(m//index)
                    break
            index += 1
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    S = [tuple(map(int, input().split())) for _ in range(n)]
    S.sort(key=lambda x: -x[1])
    y_1, y_0 = [], []
    st = set()
    for t, d in S:
        if t in st:
            y_0.append(d)
        else:
            st.add(t)
            y_1.append(d)

    max_sum = -1
    for number_of_y_1 in range(len(y_1)+1):
        if number_of_y_1 > k:
            break
        current_sum = 0
        number_of_y_0 = k - number_of_y_1
        current_sum += sum(y_1[:number_of_y_1])
        current_sum += sum(y_0[:number_of_y_0])
        current_sum += number_of_y_1 ** 2
        if max_sum == -1:
            max_sum = current_sum
        else:
            if max_sum < current_sum:
                max_sum = current_sum
    print(max_sum)
    return


if __name__ == '__main__':
    main()

### FIXED CODE ###


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

import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    S = [tuple(map(int, input().split())) for _ in range(n)]
    S.sort(key=lambda x: -x[1])
    y_1, y_0 = [0], [0]
    st = set()

    for t, d in S:
        if t in st:
            #累積報酬和のリスト
            y_0.append(y_0[-1]+d)
        else:
            st.add(t)
            y_1.append(y_1[-1]+d)
    

    max_sum = -1

    for i in range(1,k+1):
        if k-i >= len(y_0):
            continue
        if i >= len(y_1):
            break
        max_sum = max(max_sum, y_0[k-i]+y_1[i]+i**2)
    
    print(max_sum)
    return


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

from itertools import combinations
from heapq import heappush, heappop

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
N += 2
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
E = [[float('inf')] * N for _ in range(N)]
for v in range(N): E[v][v] = 0
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    E[i][j] = E[j][i] = d
dist = [float('inf')] * N # the distance of each vertex from s
visited = [False] * N
n_visited = 0 # #(visited vertices)
heap = []
heappush(heap, (0, -1, 0))
while heap:
    d, p, v = heappop(heap)
    if visited[v]: continue # (s,v)-shortest path is already calculated
    dist[v] = d; visited[v] = True
    n_visited += 1
    if n_visited == N: break
    for u in range(N):
        if visited[u]: continue
        temp = d + E[v][u]
        if dist[u] > temp: heappush(heap, (temp, v, u))
print(dist[1])

### FIXED CODE ###

from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])