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

from heapq import *
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)
for i in range(M):
    B, C = map(int, input().split())
    cnt = 0
    while cnt < B and cnt < N:
        x = heappop(A)
        if x < C:
            heappush(A, C)
        else:
            heappush(A, x)
            break
        cnt += 1
ans = 0
while len(A) > 0:
    ans += heappop(A)
print(ans)

### FIXED CODE ###

from heapq import *
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)
B_C = [list(map(int, input().split())) for i in range(M)]
B_C.sort(key = lambda x : x[1], reverse = True)
for i in range(M):
    cnt = 0
    while cnt < B_C[i][0]:
        x = heappop(A)
        if x < B_C[i][1]:
            heappush(A, B_C[i][1])
        else:
            heappush(A, x)
            break
        cnt += 1
print(sum(A))
### BUGGY CODE ###

k = int(input())

if k % 2 == 0:
    print(-1)
else:
    ans = 1
    num = 7 % k
    temp = 7 % k
    while True:
        if num % k == 0:
            print(ans)
            break
        else:
            ans += 1
            temp = temp * 10 % k
            num += temp % k
            num %= k


### FIXED CODE ###

k = int(input())

if k % 2 == 0 or k % 5 == 0:
    print(-1)
else:
    ans = 1
    num = 7 % k
    temp = 7 % k
    while True:
        if num % k == 0:
            print(ans)
            break
        else:
            ans += 1
            temp = temp * 10 % k
            num += temp % k
            num %= k
### BUGGY CODE ###

import copy
from sys import stdin
n=int(input())
A=[int(stdin.readline().rstrip()) for _ in range(n)]
for j in range(0,n):
    B=copy.copy(A)
    s=A[j]
    A.pop(j)
    print(max(A))
    A = copy.copy(B)

### FIXED CODE ###

import copy
from sys import stdin
n=int(input())
A=[int(stdin.readline().rstrip()) for _ in range(n)]
z=max(A)
B=sorted(A)
o=B[n-2]
for j in range(0,n):
    if A[j]<z:
       print(z)
    else:
        if B[n-2]==B[n-1]:
           print(z)
        else:
           print(o)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N = int(input())

    for n in range(1, N + 1):
        res = 0
        for x in range(1, int(pow(n, 0.5)) + 1):
            for y in range(1, int(pow(n, 0.5)) + 1):
                for z in range(1, int(pow(n, 0.5)) + 1):
                    if pow(x, 2) + pow(y, 2) + pow(z, 2) + x * y + y * z + z * x == n:
                        res += 1
        print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())

    res = [0] * (n + 10)
    for x in range(1, int(pow(n, 0.5)) + 1):
        for y in range(1, int(pow(n, 0.5)) + 1):
            for z in range(1, int(pow(n, 0.5)) + 1):
                t = pow(x, 2) + pow(y, 2) + pow(z, 2) + x * y + y * z + z * x
                if t <= n:
                    res[t] += 1

    for x in range(1, n + 1):
        print(res[x])


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

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

stepper = 0
gate = []

for j in range(M):
    gate_1, gate_2 = map(int, input().split())
    gate.append([gate_1, gate_2])


def judge(num):
    num += 1
    counter = 0
    for k in gate:
        if k[0] <= num <= k[1]:
            counter += 1
    if counter == M:
        return 1
    else:
        return 0


ans = map(judge, range(N))
print(sum(list(ans)))
"""
for i in range(N):
    i += 1
    counter = 0
    for k in gate:
        #print(k, i)
        if k[0] <= i <= k[1]:
            counter += 1
    #print(counter, M)
    if counter == M:
        stepper += 1
"""


### FIXED CODE ###

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

stepper = 0
gate = []

for j in range(M):
    gate_1, gate_2 = map(int, input().split())
    gate.append([gate_1, gate_2])

gate_min = 0
gate_max = N

for m in range(M):
    if gate[m][0] > gate_min:
        gate_min = gate[m][0]

    if gate[m][1] < gate_max:
        gate_max = gate[m][1]

#print(gate_min, gate_max)
for k in range(N):
    k = k+1
    if gate_min <= k <= gate_max:
        stepper += 1

print(stepper)
### BUGGY CODE ###

N, K = map(int, input().split())
x = N
while x > K/2:
  x = abs(K-x)
print(x)


### FIXED CODE ###

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

while x > K/2:
    x = abs(K-x)

print(x)
### BUGGY CODE ###

s = input()
n = len(s)
n = max((n, 3))
x, y = map(int, input().split())
dpx = [[False] * 2 * (n + 1) for i in range(n)]
dpy = [[False] * 2 * (n + 1) for i in range(n)]

def c(s, si):
    ret = 0
    while si < len(s) and s[si] == 'F':
        ret += 1
        si += 1
    if si < len(s) and s[si] == 'T':
        si += 1
    return si, ret

si, d = c(s, 0)
dpx[0][n] = True
dpx[1][d+n] = True
dpy[0][n] = True
dp = [dpx, dpy]
turn = 0
while si < len(s):
    si, d = c(s, si)
    turn += 1
    nn = si
    for i in range(-nn, nn+1):
        if -n <= i + d <= n:
            dp[turn%2][turn//2+1][i+d+n] = dp[turn%2][turn//2+1][i+d+n] \
                    or dp[turn%2][turn//2][i+n]
        if -n <= i - d <= n:
            dp[turn%2][turn//2+1][i-d+n] = dp[turn%2][turn//2+1][i-d+n] \
                    or dp[turn%2][turn//2][i+n]

if dpx[(turn-1)//2+2][x+n] and dpy[(turn-1)//2+1][y+n]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = input()
x, y = map(int, input().split())
hL = len(s)
L = 2 * hL

dp = [[False] * (L + 1) for i in range(2)]
ndp = [False] * (L + 1)

def next(i):
    global s
    while i < hL and s[i] != 'T':
        i += 1
    i += 1
    return i

def c(x):
    global hL
    return x + hL

index = 0
t = 0
js = [1]
dp[0][c(0)] = True
dp[1][c(0)] = True
mini, maxi = 0, 1
while index < hL:
    ni = next(index)
    dx, index = ni - index - 1, ni
    for i in range(mini, maxi):
        for j in js:
            if -hL <= i + j * dx <= hL:
                nx = c(i + j * dx)
                ndp[nx] = ndp[nx] or dp[t][c(i)]
    for i in range(mini, maxi):
        dp[t][c(i)] = False
    dp[t], ndp = ndp, dp[t]
    mini, maxi = mini - dx, maxi + dx
    js = [-1, 1]
    t = (t + 1) % 2
print('Yes' if dp[0][c(x)] and dp[1][c(y)] else 'No')
### BUGGY CODE ###

n = int(input())
l = tuple(map(int, input().split()))
s = []
for i in range(n - 1):
    for j in range(i + 1, n):
        s.append([l[i] + l[j], i, j])

m = len(s)
ans = (n * (n - 1) * (n - 2)) // 6

for i in range(n):
    for j in range(m):
        if s[j][1] == i or s[j][2] == i:
            continue
        elif l[i] >= s[j][0]:
            ans -= 1
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = sorted(list((map(int, input().split()))))

cnt = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        cnt += max(0, bisect.bisect_left(l, l[i] + l[j]) - j - 1)
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def main():
    N = list(map(int, open(0).read().split()))
    N = N[0]
    L = 0

    for a in range(1, N+1):
        for b in range(1, N+1):
            for c in range(1, N+1):
                L += gcd(a,b,c)
    print(L)
main()

### FIXED CODE ###

#!/usr/bin/env python3
import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
def main():
    N = list(map(int, open(0).read().split()))
    N = N[0]
    L = 0
 
    for a in range(1, N+1):
        for b in range(1, N+1):
            for c in range(1, N+1):
                L += gcd(a,b,c)
    print(L)
main()
### BUGGY CODE ###

N = int(input())
E = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
K = 0
E_sorted = sorted(E, key=lambda x:x[0])
ans = {}
V = [[] for _ in range(N)]
for e in E_sorted:
  a, b = e
  c = 1
  req_K = True
  c = 1
  i = 1
  while i <= K:
    if not (i in V[a]):
      c = i
      req_K = False
      break
    i += 1
  if req_K:
    K += 1
    c = K
  V[a].append(c)
  V[b].append(c)
  ans[e] = c
print(K)
for e in E:
  print(ans[e])


### FIXED CODE ###

from collections import OrderedDict
N = int(input())
color_parents = [0] * N
tree = [[] for _ in range(N)]
color = OrderedDict()
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  color[(a, b)] = 0
for a in range(N):
  c_p = color_parents[a]
  c = 1
  for b in tree[a]:
    if c == c_p:
      c += 1
    color[(a, b)] = c
    color_parents[b] = c
    c += 1
print(max(color.values()))
for k in color.keys():
  print(color[k])
### BUGGY CODE ###


if __name__ == '__main__':
    N=int(input())
    sheet=[]
    for i in range(N):
        temp=int(input())
        if temp not in sheet:
            sheet.append(temp)
        else:
            sheet.remove(temp)

    print(len(sheet))

### FIXED CODE ###


if __name__ == '__main__':
    N=int(input())
    sheet=[]
    for i in range(N):
        temp=int(input())
        sheet.append(temp)
    sheet.sort()
    count=0
    i=0
    while i<N:
        s=sheet[i]
        j=i
        while i<N and sheet[i]==s:
            i+=1
        d=i-j
        if d%2==1:
            count+=1

    print(count)
### BUGGY CODE ###

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

a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = val[0] + val[1]
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)

print(ans%(10**9+7))

### FIXED CODE ###

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

a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = val[-2] + val[-1]
    val.append(ans)
    if len(a) > 0:
        if i == a[0]:
            val[-1] = 0
            a.pop(0)

print(ans % (10**9 +7))
### BUGGY CODE ###

#coding: utf-8
N, Q = map(int, input().split())
S = list(input())
for i in range(Q):
    q1 = list(map(int, input().split()))
    cnt = 0
    qs = S[q1[0]-1:q1[1]]
    for j in range(len(qs)-1):
        if qs[j] == "A" and qs[j+1] == "C":
            cnt += 1
    print(cnt)

### FIXED CODE ###

#coding: utf-8
N, Q = map(int, input().split())
S = input()
T = [0]
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        T.append(T[i] + 1)
    else:
        T.append(T[i])
for j in range(Q):
    l, r = map(int, input().split())
    print(T[r-1] - T[l-1])
### BUGGY CODE ###

def heapify(values):
  n = len(values)
  for i in range(1,n):
    upheap(values,i)
    print(' '.join(map(str, values)))

def upheap(values, i):
  while parent(i) >= 0:
    if values[i] > values[parent(i)]:
      values[i], values[parent(i)] = values[parent(i)], values[i]
      i = parent(i)
    else:
      break

def pop(values):
  ret = values[0]
  values[0], values[len(values)-1] = values[len(values)-1], values[0]
  del values[len(values)-1]
  downheap(values)
  return ret

def push(values, x):
  values.append(x)
  upheap(values, len(values)-1)

def downheap(values):
  i = 0
  while left(i) < len(values) or right(i) < len(values):
    l = left(i)
    r = right(i)
    if l >= len(values):
      m = r
    elif r >= len(values):
      m = l
    else:
      m = r
      if values[l] > values[r]:
        m = l
    if values[i] < values[m]:
      values[m], values[i] = values[i], values[m]
    i = m

def parent(i):
  i = i+1
  return i//2-1

def left(i):
  i = i+1
  return i*2-1

def right(i):
  i = i+1
  return i*2

values = []
while True:
  line = input()
  if line.startswith('end'):
    break
  elif line.startswith('extract'):
    print(pop(values))
  elif line.startswith('insert'):
    num = int(line.split(' ')[1])
    push(values, num)

### FIXED CODE ###

from sys import stdin

def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= A[0] and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

heap = [0]*2000000
for c in stdin:
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break
### BUGGY CODE ###

import numpy
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = numpy.array(list(map(int, input().split())))
for _ in range(m):
    b = numpy.argmax(a)
    a[b] = a[b]//2
print(sum(a))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    b = heapq.heappop(a)//(-2)
    heapq.heappush(a,-b)
print(-sum(a))
### BUGGY CODE ###

from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3)
        for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
maze = [input() for _ in range(H)]

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.appendleft((sx, sy, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s:
            d[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.appendleft((nx, ny, s+1))

ans = d[gx][gy] if d[gx][gy] < INF else -1
print(ans)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M=map(int,input().split())
list1=list(map(int,input().split()))
for _ in range(M):
  B,C=map(int,input().split())
  list1+=[C]*B
  while len(list1)>=N+1:
    list1.remove(min(list1))
SUM=sum(list1)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###

k = int(input())
s = input()
MOD = 10**9+7

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

ans = 0
for i in range(len(s),len(s)+k+1):
  tmp = nCr(i-1,len(s)-1)*pow(25,i-len(s),MOD)
  tmp %= MOD
  tmp *= pow(26,len(s)+k-i,MOD)
  tmp %= MOD
  ans +=tmp
  ans %= MOD
print(ans)

### FIXED CODE ###

k = int(input())
s = input()
MOD = 10**9+7

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

p25 = [1]
for i in range(len(s)+k):
  p25.append((p25[-1]*25)%MOD)
p26 = [1]
for i in range(len(s)+k):
  p26.append((p26[-1]*26)%MOD)

ans = 0
for i in range(len(s),len(s)+k+1):
  tmp = nCr(i-1,len(s)-1)*p25[i-len(s)]
  tmp %= MOD
  tmp *= p26[len(s)+k-i]
  tmp %= MOD
  ans +=tmp
  ans %= MOD
print(ans)
### BUGGY CODE ###

def deep_search(L,i,f):
    Q=L[i]
    if f[i]==0:
        f[i]=i
        for j in L[i]:
            f[j]=i
        while Q!=[]:
            p=Q.pop()
            Q=Q+L[p]
            for j in L[p]:
                f[j]=i
    return f

N,K,L=input().split(" ")
N=int(N)
K=int(K)
L=int(L)
a=[0 for i in range(N+1)]
b=[0 for i in range(N+1)]
road=[[] for i in range(N+1)]
train=[[] for i in range(N+1)]
for i in range(K+L):
    p,q=input().split(" ")
    p=int(p)
    q=int(q)
    if i<K:
        road[p].append(q)
    else:
        train[p].append(q)
for i in range(1,N+1):
    a=deep_search(road,i,a)
    b=deep_search(train,i,b)
ans=[]
for i in range(1,N+1):
    time=0
    for j in range(1,N+1):
        if a[i]==a[j] and b[i]==b[j]:
            time+=1
    print(time,end=" ")



### FIXED CODE ###

from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]


    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)



count=defaultdict(lambda:0)
point=[]
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    point.append(l)
    count[str(l)]+=1
for i in point:
    print(count[str(i)],end=" ")
### BUGGY CODE ###

S = input()
Q = int(input())
flag_reversed = False
ret = S
for _ in range(Q):
    temp = input()
    if (len(temp) == 1):
        flag_reversed = not flag_reversed
    else:
        T, F, C = [x for x in temp.split(" ")]
        F = int(F)
        add_begin = True
        if (F == 2):
            add_begin = False
        if (flag_reversed):
            add_begin = not add_begin
        if (add_begin):
            ret = C + ret
        else:
            ret += C

if (flag_reversed):
    ret = ret[::-1]
print(ret)



### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
flag_reversed = False
ret = deque(S)

for _ in range(Q):
    temp = input()
    if (len(temp) < 2):
        flag_reversed = not flag_reversed
    else:
        T, F, C = [x for x in temp.split(" ")]
        F = int(F)
        add_begin = True
        if (F == 2):
            add_begin = False
        if (flag_reversed):
            add_begin = not add_begin
        if (add_begin):
            ret.appendleft(C)
        else:
            ret.append(C)

ret = ''.join(ret)

if (flag_reversed):
    ret = ''.join(reversed(ret))
print(ret)
### BUGGY CODE ###

s=input().rstrip()
ans=[0 for i in range(2019)]
tmp=0
a=0
for i in reversed(s):
    ans[tmp%2019]+=1
    tmp=tmp+int(i)*10**a
    a+=1
ans[tmp%2019]+=1
count=0
for i in ans:
    count+=int(i*(i-1)/2)
print(count)

### FIXED CODE ###

s=input().rstrip()
ans=[0 for i in range(2019)]
tmp=0
a=1
rs=reversed(s)
for i in rs:
    ans[tmp%2019]+=1
    tmp=(tmp+int(i)*a)%2019
    a*=10
    a%=2019
ans[tmp%2019]+=1
count=0
for i in ans:
    count+=int(i*(i-1)/2)
print(count)
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist


def main():
    xs, ys, xt, yt = map(int, input().split())
    N = int(input())
    br = [[xs, ys, 0], [xt, yt, 0]]
    for _ in range(N):
        br.append(list(map(int, input().split())))

    adj = [[] for _ in range(N+3)]
    for i in range(N+2):
        for j in range(i+1, N+2):
            dij = max(((br[i][0] - br[j][0])**2 + (br[i][1] - br[j][1])**2) ** (1/2) - (br[i][2] + br[j][2]), 0)
            adj[i+1].append([j+1, dij])
            adj[j+1].append([i+1, dij])

    print(dijkstra(adj, 1)[2])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        # if v_from == 2:
        #    return dist
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist


def main():
    xs, ys, xt, yt = map(int, input().split())
    N = int(input())
    br = [(xs, ys, 0), (xt, yt, 0)]
    for _ in range(N):
        br.append(tuple(map(int, input().split())))

    adj = [[] for _ in range(N+3)]
    for i in range(N+2):
        for j in range(i+1, N+2):
            dij = max(((br[i][0] - br[j][0])**2 + (br[i][1] - br[j][1])**2) ** (1/2) - (br[i][2] + br[j][2]), 0)
            adj[i+1].append([j+1, dij])
            adj[j+1].append([i+1, dij])

    print(dijkstra(adj, 1)[2])


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

import numpy as np


def count_multi(s, d):
  a = np.array([int(c) for c in s])
  m = a % d
  keta = 1
  count = np.count_nonzero(m == 0)
  while len(m) > 1:
    m = (10*m[:-1] + a[keta:]) % d
    keta += 1
    count += np.count_nonzero(m == 0)
  return count
        
print(count_multi(input(), 2019))


### FIXED CODE ###

def main():
    mod = 2019
    count = [0] * 2019
    count[0] = 1
    s = input().strip()
    digit = 1
    current = 0
    for c in s[::-1]:
        current = (current + int(c) * digit) % mod
        count[current] += 1
        digit = digit * 10 % mod
    return sum([n * (n - 1) // 2 for n in count if n > 1])


print(main())
### BUGGY CODE ###

n = int(input())
s = input()
 
m = [[0] * n for _ in range(n)]
lcs = 0

for j in range(1, n):
    if s[j] == s[0]:
        m[0][j] = 1
        lcs = 1

for i in range(1, n-1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            m[i][j] = min(m[i-1][j-1] + 1, j - i)
            lcs = max(m[i][j], lcs)
        else:
            m[i][j] = 0

print(lcs)

### FIXED CODE ###

tmp = input()
my_str = input()
 
start = 0
end = 1
max_len = 0
 
while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
        end += 1
    else:
        start += 1
print(max_len)