Harryxun/stf_run huggingface dataset:
S = input()

now = S[0]
i = 1
mozi_list = [now]
num = 1
while i < len(S):
	#print(i, mozi_list)
	if i != len(S) - 1:
		if len(now) == 1:
			if now != S[i]:
				now = S[i]
				mozi_list.append(now)
				i += 1
				num += 1
			else:
				now = S[i:i + 2]
				mozi_list.append(now)
				i += 2
				num += 1
		if len(now) == 2:
			now = S[i]
			mozi_list.append(now)
			i += 1
			num += 1
	else:
		if len(now) == 2:
			now = S[i]
			mozi_list.append(now)
			i += 1
			num += 1
		elif now != S[i]:
			now = S[i]
			mozi_list.append(now)
			i += 1
			num += 1
		else:
			i += 1

print(num)

### FIXED CODE ###

S = input()

now = S[0]
i = 1
mozi_list = [now]
num = 1
while i < len(S):
	#print(i, mozi_list)
	if i != len(S) - 1:
		if len(now) == 1:
			if now != S[i]:
				now = S[i]
				mozi_list.append(now)
				i += 1
				num += 1
			else:
				now = S[i:i + 2]
				mozi_list.append(now)
				i += 2
				num += 1
		elif len(now) == 2:
			now = S[i]
			mozi_list.append(now)
			i += 1
			num += 1
	else:
		if len(now) == 2:
			now = S[i]
			mozi_list.append(now)
			i += 1
			num += 1
		elif now != S[i]:
			now = S[i]
			mozi_list.append(now)
			i += 1
			num += 1
		else:
			i += 1

print(num)
N, M = list(map(int, input().split()))

questions = [False] * N
ac_count = penalty_count = 0
P = []
S = []

for _ in range(M):
    p, s = list(input().split())
    p = int(p) - 1

    P.append(p)
    S.append(s)

    if s == 'AC':
        questions[p] = True

for i in range(M):
    if S[P[i]] == 'WA' and questions[P[i]]:
        penalty_count += 1

print(sum(questions), penalty_count)

### FIXED CODE ###

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

is_solved = [False] * N
wa_count = [0] * N
wa_total = 0

for _ in range(M):
    p, s = list(input().split())
    p = int(p) - 1

    if s == 'AC':
        if not is_solved[p]:
            is_solved[p] = True
            wa_total += wa_count[p]
    else:
        wa_count[p] += 1

print(sum(is_solved), wa_total)
n = int(input())
a = list(map(int, input().split()))

l = []
for i in range(n):
    x = l.index(i + 1) + 1
    l.append(x)
    
print(' ', join(l))


### FIXED CODE ###

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

l = [0] * n

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

print(*l)
a = list(map(int, input().split()))
s = [input() for i in range(a[0])]
newa= sorted(s)
print(a[0],a[1])
[print(i) for i in newa]




### FIXED CODE ###

a= input().split()
if a.count('5')==2 and a.count('7')==1:
            print('YES')
else:
            print('NO')
rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [0 for i in range(n)]

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]


edgeList.sort(key=lambda x: x[0])
flag = True
while flag:
    flag = False
    for e in edgeList:
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == 0 != y:
            parent[e[2]] = e[1]
            lenList[e[2]] += lenList[e[1]] + e[0]
            rootList[y] = 0
            flag = True
            break

for i, j in zip(range(n), lenList):
    print(i, j)

### FIXED CODE ###

n = int(input())
edgeList = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(a[1]):
        edgeList.append([a[2*j+3], i, a[2*j+2]])
 
 
rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [float("inf") for i in range(n)]
lenList[0] = 0
def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
 
flag = True
while flag:
    flag = False
    edgeList.sort(key=lambda x: (x[0] + lenList[x[1]]))
    for e in edgeList:    # weight:e[0], e[1]->e[2]
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == 0 != y:
            parent[e[2]] = e[1]
            lenList[e[2]] = lenList[e[1]] + e[0]
            rootList[y] = 0
            flag = True
            break
 
for i, j in zip(range(n), lenList):
    print(i, j)
num_list=int(input())
a=[int(x) for x in input().split()]
print(a)
for i in range(num_list):
  b=[int(x) for x in input().split()]
  print(b)
  if (abs(b[1]-a[1])+abs(b[2]-a[2]))<=(b[0]-a[0]):
    if i+2 == num_list:
      print("Yes")
      break
    a=b
    continue
  else:
    print("No")
    break

### FIXED CODE ###

num_list=int(input())
a=[0,0,0]
for i in range(num_list):
  b=[int(x) for x in input().split()]
  dt=(b[0]-a[0])
  d=(abs(b[1]-a[1])+abs(b[2]-a[2]))
  if d<=dt and dt%2==d%2:
    if i == num_list-1:
      print("Yes")
      break
    a=b
  else:
    print("No")
    break
for i in range(n):
    b.append(a[i]//400)
for i in range(13):
    if b.count(i) >=1:
        if i<= 7:
            countmax +=1
            countmin +=1
        else:
            countmax += b.count(i)
print(countmin,countmax)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b =[]
countmax = 0
countmin = 0

for i in range(n):
    b.append(a[i]//400)
for i in range(13):
    if b.count(i) >=1:
        if i<= 7:
            countmax +=1
            countmin +=1
        else:
            countmax += b.count(i)
print(max(1,countmin),countmax)
from collections import Counter, defaultdict, deque


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

al = list(map(int, input().split()))

if n == 1 and al[0] == 0:
    print(1)
elif n == 2:
    if 0 not in al:
        print(2)
    else:
        print(0)

if n % 2 == 0:
    lst = [0] * n
    for i in range(1, n):
        x = (al[i - 1] + n - 1) / 2
        y = x - al[i - 1]
        # print(x,y)
        # print(n-x-1,x)
        lst[int(n - x - 1)] += 1
        lst[int(x)] += 1
        if (lst[int(n - x - 1)] or lst[int(x)]) >= 3:
            print(0)
            exit()
    # print(lst)
    if 0 not in lst:
        print(int(2 ** (n / 2)) % ((10 ** 9) + 7))
    else:
        print(0)
else:
    lst = [0] * n
    for i in range(1, n):
        x = (al[i - 1] + n - 1) / 2
        y = x - al[i - 1]
        # print(x,y)
        # print(n - x - 1, x)
        if x == y:
            lst[int(x)] += 1
        else:
            lst[int(n - x - 1)] += 1
            lst[int(x)] += 1
        if (lst[int(n - x - 1)] or lst[int(x)]) >= 3:
            print(0)
            exit()
    # print(lst)
    if 0 not in lst:
        print(int(2 ** ((n - 1) / 2)) % ((10 ** 9) + 7))
    else:
        print(0)


### FIXED CODE ###

from collections import Counter

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

c_al = Counter(al)

if n % 2 == 0:
    for k,v in c_al.items():
        if v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))

elif n % 2 != 0:
    for k, v in c_al.items():
        if k == 0:
            if v != 1:
                print(0)
                exit()
        elif v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))
import sys
input = sys.stdin.readline
a = [0,0,0,0,0]
b = [[0,i] for i in range(5)]
for i in range(5):
    a[i] = int(input())
    b[i][0] = a[i] % 10
b.sort()
j = 0
while b[j][0] == 0:
    j += 1
time = 0
for i in range(5):
    if i != b[j][1]:
        if a[i] % 10 == 0:
            time += a[i]
        else:
            time += (a[i] + (10 - a[i] % 10))
time += a[b[j][1]]
print(time)

### FIXED CODE ###

import sys
input = sys.stdin.readline
a = [0,0,0,0,0]
b = [[0,i] for i in range(5)]
for i in range(5):
    a[i] = int(input())
    b[i][0] = a[i] % 10
b.sort()
j = 0
while j < 5 and b[j][0] == 0:
    j += 1
time = 0
if j == 5:
    for i in range(5):
        time += a[i]
else:
    for i in range(5):
        if i != b[j][1]:
            if a[i] % 10 == 0:
                time += a[i]
            else:
                time += (a[i] + (10 - a[i] % 10))
    time += a[b[j][1]]
print(time)
from itertools import permutations
N, M, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
V = N
# Define infinity as the large enough value. This value will be
# used for vertices not connected to each other
INF  = 10000000
 
graph = [[INF for i in range(N)] for j in range(N)]
 
for m in range(M):
    A, B, C  = [int(i) for i in input().split()]
    A = A - 1
    B = B - 1
    graph[A][B] = C
    graph[B][A] = C
 
# Solves all pair shortest path via Floyd Warshall Algrorithm
def floydWarshall(graph):
    dist = graph
    for k in range(V):
 
        # pick all vertices as source one by one
        for i in range(V):
 
            # Pick all vertices as destination for the
            # above picked source
            for j in range(V):
 
                # If vertex k is on the shortest path from 
                # i to j, then update the value of dist[i][j]
                dist[i][j] = min(dist[i][j] ,
                                  dist[i][k]+ dist[k][j]
                                )
    return(dist)
 
new_graph = floydWarshall(graph)
smallest_dist = INF
for sub_permute in permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += new_graph[sub_permute[i]][sub_permute[i+1]]
    smallest_dist = min(smallest_dist, tmp)
print(smallest_dist)

### FIXED CODE ###

N = input()
if '9' in N:
    print('Yes')
else:
    print('No')
a, b, c, k = map(int, input().split())

if (a >= k):
    print(k)
elif ((a + b) >= k):
    print(a)
else:
    max_num = a - (k - a - b)
    print(max_num)

### FIXED CODE ###

x = input()
y = input()
 
if x == y[:-1]:
	print('Yes')
else:
	print('No')
##======================================python3
''' ===========================================
## null
##
##
=========================================== '''
import sys
from sys import stdin #read(), readline()
input = stdin.readline
import heapq #heappush(trgt, val) heappop(trgt) trgt[0] __lt__<
sys.setrecursionlimit(10**6)
INF = 1<<50

if __name__ == '__main__':
    n = int(input())
    
    chk = True;
    
    iip = list(map(int, input().split(' ')))
    for i in range(n):
        a = iip[i]
        if a&1 == 0:
            if a%3 == 0 or a%5 == 0:
                continue;
            else:
                chk = False;
                break;
        else:
            continue;
    
    if chk == True:
        print("APPROVED")
    else:
        print(DENIED)
    

### FIXED CODE ###

##======================================python3
''' ===========================================
## null
##
##
=========================================== '''
import sys
from sys import stdin #read(), readline()
input = stdin.readline
import heapq #heappush(trgt, val) heappop(trgt) trgt[0] __lt__<
sys.setrecursionlimit(10**6)
INF = 1<<50

if __name__ == '__main__':
    n = int(input())
    
    chk = True;
    
    iip = list(map(int, input().split(' ')))
    for i in range(n):
        a = iip[i]
        if a&1 == 0:
            if a%3 == 0 or a%5 == 0:
                continue;
            else:
                chk = False;
                break;
        else:
            continue;
    
    if chk == True:
        print("APPROVED")
    else:
        print("DENIED")
A, B = int(input())

if A==B:
	print('Draw')
elif A>B or A==1:
	print('Alice')
else:
	print('Bob')

### FIXED CODE ###

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

if A==1:
	if A==B:
		print('Draw')
	else:
		print('Alice')
elif B==1:
	print('Bob')
else:
	if A==B:
		print('Draw')
	elif A>B:
		print('Alice')
	else:
		print('Bob')
s = input()
for i in range(len(s)):
  if s[i]=='1':
    s[i]='9'
  else:
    s[i]='1'

print(s)

### FIXED CODE ###

s = input()
s = s.replace('1','2')
s = s.replace('9','1')
s = s.replace('2','9')
print(s)
n, m = map(int, input().split())
sc = [map(int, input().split()) for i in range(m)]
s, c = [list(i) for i in zip(*sc)]

for i in range (10**(n-1),10**n):
    p = str(i)
    flag = 0
    for j in range(m):
        if p[s[j]-(4-n)] != str(c[j]):
            flag = 1
            break

    if flag == 0:
        print(i)
        flag = 2
        break

if flag != 2:
    print("-1")

### FIXED CODE ###

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

flag = 0

if m != 0:
    s, c = [list(i) for i in zip(*sc)]


    if n == 1:
        for i in range (0,10):
            p = str(i)
            flag = 0
            for j in range(m):
                if p[s[j]-1] != str(c[j]):
                    flag = 1
                    break

            if flag == 0:
                print(i)
                flag = 2
                break
    else:
        for i in range (10**(n-1),10**n):
            p = str(i)
            flag = 0
            for j in range(m):
                if p[s[j]-1] != str(c[j]):
                    flag = 1
                    break

            if flag == 0:
                print(i)
                flag = 2
                break

if flag != 2:
    if m == 0:
        if n == 1:
            print("0")
        elif n == 2:
            print("10")
        else:
            print("100")
    else:
        print("-1")
N = str(input()) #ここで標準入力

car = ''
if N[-1] == 3:
    car = 'bon'
elif N[-1] == 0 or N[-1] == 1 or N[-1] == 6 or N[-1] == 8
    car = 'pon'

print(car)

### FIXED CODE ###

N = str(input()) #ここで標準入力

car = ''
if N[-1] == '3':
    car = 'bon'
elif N[-1] == '0' or N[-1] == '1' or N[-1] == '6' or N[-1] == '8':
    car = 'pon'
else:
    car = 'hon'



print(car)
n = int(input())
t = [[] for _ in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  t[a-1].append((b-1,c))
  t[b-1].append((a-1,c))
q,k = map(int,input().split())
k -= 1
l = [0]*n
def dfs(a,b,c):
  for i,j in t[b]:
    if i != a:
      l[i] = c+j
      dfs(b,i,c+j)
dfs(-1,k,0)
for _ in range(q):
  x,y = map(lambda x:int(x)-1,input().split())
  print(l[x]+l[y])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
n = int(input())
t = [[] for _ in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  t[a-1].append((b-1,c))
  t[b-1].append((a-1,c))
q,k = map(int,input().split())
k -= 1
l = [0]*n
def dfs(a,b,c):
  for i,j in t[b]:
    if i != a:
      l[i] = c+j
      dfs(b,i,c+j)
dfs(-1,k,0)
for _ in range(q):
  x,y = map(lambda x:int(x)-1,input().split())
  print(l[x]+l[y])
a,b = map(int, input(),split())
print("{}".format(a-b+1))

### FIXED CODE ###

a,b = map(int, input().split())
print("{}".format(a-b+1))
n, x = map(int, input( ).split())
a = []
for i in range(n):
  k = input().split( )[i]
  a.append(int(k))
counter = 0
for i in a.sort():
  x -= i
  if x <0:
    print(counter)
  else:
    counter += 1

### FIXED CODE ###

n, x = map(int, input( ).split())
a = list(map(int, input().split()))
counter = 0
for i in sorted(a):
  x -= i
  counter += 1
  if x<0:
    print(counter-1)
    break
  elif x==0:
    print(counter)
    break
  else:
    if counter==n:
      print(counter-1)
#!/usr/bin/env python

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7

    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        l = 0
        r = -1
        mlt1 = a[0] * a[1]
        mlt2 = a[-2] * a[-1]
        for _ in range(k//2):
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                l += 2
                if l <= n-1:
                    mlt1 = a[l+1] * a[l]
            else:
                ret *= mlt2 % mod
                r -= 2
                if r >= -n+1:
                    mlt2 = a[r-1] * a[r]
            ret %= mod

        if k % 2 == 1:
            ret *= a[r]
            ret %= mod

    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7

    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        l = 0
        r = -1
        mlt1 = a[0] * a[1]
        mlt2 = a[-2] * a[-1]
        for _ in range(k//2):
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                l += 2
                if l <= n-2:
                    mlt1 = a[l+1] * a[l]
            else:
                ret *= mlt2 % mod
                r -= 2
                if r >= -n+1:
                    mlt2 = a[r-1] * a[r]
            ret %= mod

        if k % 2 == 1:
            ret *= a[r]
            ret %= mod

    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod

    print(ret)


if __name__ == '__main__':
    main()
n = int(input())
lsx = []
lsy = []
ans = 0
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
if n==1:
    a = int(input())
    for i in range(a):
    	x,y=map(int,input().split())
      if y==0:
          print(0)
      else:
          print(1)
      break
else:
    for i in range(n):
        a = int(input())
        for j in range(a):
            x,y = map(int,input().split())
            lsx.append(x)
            lsy.append(y)
            if x in lsx:
                p = 0
                p2 = 0
                for k in my_index_multi(lsx,x):
                    if lsy[k] == 1:
                        p+=1
                    else:
                        p2+=1                
                ans+=min(p,p2)
    test=0        
    for i in lsy:
        if i == 0:
            test+=1
    if test==len(lsy):
        print(1)
    else:
        print(n-ans)

### FIXED CODE ###

n = int(input())
ls = []
for i in range(n):
    a = int(input())
    p = []
    for i in range(a):
        x,y = map(int,input().split())
        p.append([x-1,y])
    ls.append(p)

ans = 0

for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i >> j) & 1:
            for k in ls[j]:
                if (i>>k[0])&1 != k[1]:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 

def main():
    N = inp()
    n = []
    while N > 0:
        n.append(N%10)
        N //= 10
    l = len(n)
    ans = 0
    for i in range(l):
        if n[i] == 10:
            n[i+1] += 1
            n[i] = 0
        if n[i] == 0:
            continue
        if n[i] <= 4:
            ans += n[i]
        elif n[i] == 5 and (i == l-1 or n[i+1] <= 4):
            ans += n[i]
        else:
            ans += 10 - n[i]
            n[i] = 0
            n[i+1] += 1
        if i == l-1:
            if n[i] == 0:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 

def main():
    n = list(input())
    l = len(n)
    ans = 0
    for i in range(l):
        n[i] = int(n[i])
    for i in range(l-1,-1,-1):
        if n[i] <= 4:
            ans += n[i]
        elif n[i] == 5 and (i == 0 or n[i-1] <= 4):
            ans += n[i]
        else:
            ans += 10 - n[i]
            n[i] = 0
            if i != 0:
                n[i-1] += 1
        if i == 0 and n[i] == 0:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()
import sys
file= lambda location: {True:sys.stdin, False:open(location,"r")}[location==""]

location="subs.txt"#Enter location here
sys.stdin=file(location)
raw_input=sys.stdin.readline

for i in xrange(int(raw_input())):
N,A,B=map(int,raw_input().split())
m=A+B
if A==B==N:
	print N,N
elif(m>N):
	if A==B:
		print A,1
	else:
		print min(A,B),abs(A-B)
else:
	print min(A,B),0




### FIXED CODE ###

N, A, B = map(int, raw_input().split())
m=A+B
print min(A, B), max(0,m-N)
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]

#print(max(((0)**2+(0)**2)**.5-0-0,0))
xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[list(map(int,input().split())) for i in range(N)]
XYR.append([xt,yt,0])#終点
XYR.append([xs,ys,0])#開始

kyori=[[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
    for m in range(i,len(XYR)):
        if i==m:
            t=0
        else:
            x1,y1,r1=XYR[i]
            x2,y2,r2=XYR[m]
            t=max(((x2-x1)**2+(y2-y1)**2)**.5-r1-r2,0)

        kyori[i][m]=t
        kyori[m][i]=t

stack=sorted(kyori[-2])
heapify(stack)
Pdic={}
dic={}
kyoriset=set()
for i in range(len(XYR)):
    a=str(kyori[-1][i])
    Pdic.update({i:a})
    if not a in kyoriset:
        kyoriset.add(a)
        dic.update({a:[i]})
    else:
        dic[a].append(i)
visited=set([len(XYR)-1])
while stack:
    m=str(heappop(stack))
    a=dic[m].pop()
    if a==len(XYR)-2:
        print(m)
        exit()
    if not a in visited:
        visited.add(a)
        for i in range(len(XYR)):
            nm=kyori[a][i]+float(m)
            nm=str(nm)
            if float(Pdic[i])>float(nm):
                Pdic[i]=nm
                heappush(stack,float(nm))
                if not nm in kyoriset:
                    kyoriset.add(nm)
                    dic.update({nm:[i]})
                else:
                    dic[nm].append(i)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
idle=10**13
xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[list(map(int,input().split())) for i in range(N)]
XYR.append([xt,yt,0])#終点
XYR.append([xs,ys,0])#開始
"""for i in range(len(XYR)):
    XYR[i][0]*=idle
    XYR[i][1]*=idle
    XYR[i][2]*=idle"""
kyori=[[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
    for m in range(i,len(XYR)):
        if i==m:
            t=0
        else:
            x1,y1,r1=XYR[i]
            x2,y2,r2=XYR[m]
            t=max(((x2-x1)**2+(y2-y1)**2)**.5-r1-r2,0)

        kyori[i][m]=t
        kyori[m][i]=t
stack=sorted(kyori[-1])
heapify(stack)
Pdic={}
dic={}
kyoriset=set()
for i in range(len(XYR)):
    a=kyori[-1][i]
    Pdic.update({i:a})
    if not a in kyoriset:
        kyoriset.add(a)
        dic.update({a:[i]})
    else:
        dic[a].append(i)
visited=set([len(XYR)-1])
while stack:
    m=heappop(stack)
    a=dic[m].pop()
    if a==len(XYR)-2:
        print(m)
        exit()
    if not a in visited:
        visited.add(a)
        for i in range(len(XYR)):
            nm=kyori[a][i]+m
            if Pdic[i]>nm:
                Pdic[i]=nm
                heappush(stack,nm)
                if not nm in kyoriset:
                    kyoriset.add(nm)
                    dic.update({nm:[i]})
                else:
                    dic[nm].append(i)