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

from itertools import combinations

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

def choose(select):
    wa = []
    ans = 0
    for combi in combinations(range(n+1), select):
        tmp_wa = 0
        for i in range(select):
            tmp_wa += combi[i]
        if tmp_wa in wa:
            continue
        else:
            wa.append(tmp_wa)
            ans += 1
    
    return ans
            

res = 0

for i in range(k, n+2):
    res += choose(i) % (pow(10, 9) + 7)

print(res)

### FIXED CODE ###

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

ans = 0

def select(l, r):
    return (l+r)*(r-l+1) // 2

for i in range(k, n+2):
    l = select(0, i-1)
    r = select(n-i+1, n)
    ans += (r-l+1) 
    ans %= (pow(10, 9) + 7)

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

n, k = map(int, input().split())
heights = list(map(int, input().split()))
dp = [float("inf") for i in range(n+2)]
dp[0] = 0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j] + abs(heights[i] - heights[i-j]))
print(dp[n-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
heights = list(map(int, input().split()))
dp = [float("inf") for i in range(n+2)]
dp[0] = 0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j] + abs(heights[i] - heights[i-j]))
print(dp[n-1])
### BUGGY CODE ###

N,K = map( int, input().split() )
H = list( map( int, input().split() ) )
dp = [0]*N
for i in range(1,N):
    dp[i] = min( [ dp[i-j] + abs( H[i] - H[i-j] ) for j in range(1,min(K+1,i+1)) ] )
print(dp[N-1])

### FIXED CODE ###

N,K = map( int, input().split() )
H = list( map( int, input().split() ) )
dp = [0]*N
for i,Hi in enumerate(H[1:],1):
    s = max(0,i-K)
    dp[i] = min( [ t + abs( Hi - hl ) for hl,t in zip(H[s:i], dp[s:i]) ] )
print(dp[N-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
while True:
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print(-1)
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

    cnt += 1

print(cnt)

### FIXED CODE ###

import time
start = time.time()

import sys
input = sys.stdin.readline

N = int(input())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
for _ in range(max_pairs // 2):
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print(-1)
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

    if time.time() - start > 1.8:
        print(N * (N - 1) // 2)
        exit()

    cnt += 1

print(cnt)
### BUGGY CODE ###

n,a,b,k=map(int,input().split())
mod=998244353
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
ans=0
for ac in range(k//a+1):
  asum=ac*a
  if (k-asum)%b:continue
  bc=(k-asum)//b
  if max(ac,bc)>n:continue
  ans=(ans+comb(n,ac)*comb(n,bc))%mod
print(ans)

### FIXED CODE ###

n,a,b,k=map(int,input().split())
mod=998244353
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
ans=0
for ac in range(k//a+1):
  asum=ac*a
  if (k-asum)%b:continue
  bc=(k-asum)//b
  if max(ac,bc)>n:continue
  ans=(ans+comb(n,ac)*comb(n,bc))%mod
print(ans)
### BUGGY CODE ###

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
b_list.sort()
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != 0:
                cnt = 0
                num = dp[i - items[b]]
                while num >= 1:
                    cnt += 1
                    num //= 10
                tmp = max(b * (10 ** cnt) + dp[i - items[b]], dp[i - items[b]] * 10 + b)
                dp[i] = max(tmp, dp[i])
print(dp[N])


### FIXED CODE ###

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}

dp = [-float("inf")] * (N + 1)
b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = 1
        b_list.append(a)

M = len(b_list)
dp[0] = 0
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != -float("inf"):
                dp[i] = max(dp[i], dp[i - items[b]] + 1)

b_list.sort(reverse=True)
ans = ""

for i in range(dp[N]):
    for b in b_list:
        if dp[N - items[b]] == dp[N] - 1:
            ans += str(b)
            N -= items[b]
            break
print(ans)
### BUGGY CODE ###

#解説参照
#言い換えが困難

n=int(input())
mod=998244353

ans=pow(3,n,mod)
rmv=0
f = [1, 1]  
inv = [1, 1]  
finv=[1,1]
for i in range(2, n+1):
    f.append((f[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    finv.append(finv[-1]*inv[-1]%mod)

def ch(a,b):
    return f[a]*finv[a-b]*finv[b]
k=n//2
if k*2<=n:
    k+=1

for i in range(k,n+1):
    ans -= ch(n,i)*pow(2,n-i+1,mod)
print(ans%mod)
    



### FIXED CODE ###

n=int(input())
mod=998244353

ans=pow(3,n,mod)
rmv=0
f = [1, 1]  
inv = [1, 1]  
finv=[1,1]
for i in range(2, n+1):
    f.append((f[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    finv.append(finv[-1]*inv[-1]%mod)

k=n//2
if k*2<=n:
    k+=1
tmp=pow(2,n-k+1,mod)
inv2=pow(2,mod-2,mod)
for i in range(k,n+1):
    ans -= f[n]*finv[n-i]*finv[i]*tmp
    tmp*=inv2
    tmp%=mod
print(ans%mod)
### BUGGY CODE ###

import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n/gg*m
aa=m/gg
bb=n/gg
ab=(m/gg)*(n/gg)
result = ll
i=0
while i < ll :
    if not (i % ab):
            tmp1=i/aa
            tmp2=i/bb
            if s[tmp1] != t[tmp2] :
                result= -1
    i+=1
print result

### FIXED CODE ###

import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n/gg*m
result = ll
for i in xrange(n):
    if not (i*m) % n :
            tmp=i*m/n
            if s[i] != t[tmp] :
                result= -1
print result
### BUGGY CODE ###

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

### FIXED CODE ###

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

import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())
AB = np.array(AB, np.int32).reshape(N - 1, 2)

a = AB[:, 0]
b = AB[:, 1]
d = np.ones_like(a, np.int32)

graph = csr_matrix((d, (a, b)), shape=(N + 1, N + 1))
takahashi, aoki = dijkstra(graph, directed=False, indices=[u, v])

print(int(aoki[takahashi < aoki].max()) - 1)

### FIXED CODE ###

import sys

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    graph[a].append(b)
    graph[b].append(a)


def dfs(v):
    dist = [-1] * (N + 1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            stack.append(w)
    return dist


DU, DV = dfs(u), dfs(v)

answer = 0
for u, v in zip(DU[1:], DV[1:]):
    if u < v:
        tmp = v - 1
        if answer < tmp:
            answer = tmp

print(answer)
### BUGGY CODE ###

dic = {"A":[],"C":[],"G":[],"T":[]}
n = int(input())
for i in range(n):
    a = input()
    t=a.split()
    if t[0] == "insert":
        dic[t[1][0]].append(t[1])
    else:
        if t[1] in dic[t[1][0]]:
            print("yes")
        else:
            print("no")
    

### FIXED CODE ###

dic=dict()
n = int(input())
for i in range(n):
    a = input()
    t=a.split()
    if t[0] == "insert":
        dic[t[1]] = True
    else:
        if t[1] in dic:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

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

cnt = 0
ans = 0
while cnt < M:
    min_cost = min(A)
    min_index = A.index(min_cost)
    amount = B[min_index]
    if cnt + amount < M:
        ans += min_cost * amount
        cnt += amount
    elif cnt + amount == M:
        ans += min_cost * amount
        break
    else:
        ans += min_cost * (M - cnt)
        break
    A = [A[i] for i in range(len(A)) if i != min_index]
    B = [B[i] for i in range(len(B)) if i != min_index]
    
print(ans)

### FIXED CODE ###

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

AB = sorted(AB)
cnt = 0
ans = 0

for e in AB:
    if cnt + e[1] < M:
        ans += e[0] * e[1]
        cnt += e[1]
    else:
        ans += e[0] * (M - cnt) 
        break

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

# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))
 
# B以下の数-A未満の数→bisect(L, B) - bisect_left(L, A)
N, K = inpl()
X = []
Y = []
Px = []
Py = []
 
for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))
 
X = sorted(X)
Y = sorted(Y)
 
dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)
 
get = itemgetter(1)
res = 5 * 10**18
 
for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    sx = sum([1 << i for i in map(get, Px[dX[l]:dX[r]+1])])
    sy = sum([1 << i for i in map(get, Py[dY[d]:dY[u]+1])])
    if bin(sx&sy).count("1") >= K:
        res = min(res, (r-l)*(u-d))
 
print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    if res < (r-l)*(u-d):
        continue

    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

print(res)
### BUGGY CODE ###

s = input()
q = int(input())
quest = [0]*q
for i in range(q):
    quest[i] = input().split()
state = 0
for que in quest:
    if (que[0] == '1'):
        # 反転は計算量が多いので一度だけする。
        state = 1 - state
        continue
    else:
        if (state == 0 and que[1] == '1'):
            s = que[2] + s
        elif(state == 0 and que[1] == '2'):
            s = s + que[2]
        elif (state == 1 and que[1] == '1'):
            s = s + que[2]
        else:
            s = que[2] + s

if (state == 1):
    s = s[::-1]
print(s)


### FIXED CODE ###

s = input()
q = int(input())
quest = [0]*q
state = 0
former, latter = '', ''
for i in range(q):
    que = input().split()
# for que in quest:
    if (que[0] == '1'):
        # 反転は計算量が多いので一度だけする。
        state = 1 - state
        continue
    else:
        if (state == 0 and que[1] == '1'):
            former = que[2] + former
        elif(state == 0 and que[1] == '2'):
            latter = latter + que[2]
        elif (state == 1 and que[1] == '1'):
            latter = latter + que[2]
        else:
            former = que[2] + former

if (state == 1):
    print(latter[::-1] + s[::-1] + former[::-1])
else:
    print(former + s + latter)
### BUGGY CODE ###

from collections import deque
from collections import defaultdict
N, M = map(int, input().split())
d = [0]*N
G = defaultdict(list)
for i in range(N-1+M):
    s, t = map(int, input().split())
    d[t-1] += 1
    G[s-1].append(t-1)
q = deque([])
for i in range(N):
    if d[i] == 0:
        q.append(i)
ans = [0]*N
cnt = []
while q:
    for i in range(len(q)):
        s = q.popleft()
        for x in cnt:
            if s in G[x]:
                ans[s] = x+1
        cnt.append(s)
        for t in G[s]:
            d[t] -= 1
            if d[t] == 0:
                q.append(t)
for x in ans:
    print(x)

### FIXED CODE ###

from collections import deque
from collections import defaultdict
N, M = map(int, input().split())
d = [0]*N
G = defaultdict(list)
for i in range(N-1+M):
    s, t = map(int, input().split())
    d[t-1] += 1
    G[s-1].append(t-1)
q = deque([])
for i in range(N):
    if d[i] == 0:
        q.append(i)
rank = [0]*N
ans = [0]*N
while q:
    s = q.popleft()
    for t in G[s]:
        d[t] -= 1
        if d[t] == 0:
            rank[t] = rank[s]+1
            q.append(t)
for i in range(N):
    for x in G[i]:
        if rank[x] - rank[i] == 1:
            ans[x] = i+1
for x in ans:
    print(x)
### BUGGY CODE ###

n, k = [int(x) for x in input().split(' ')]
exist = []
storage = [0 for x in range(10 ** 5+1)]
for i in range(n):
    a, b = [int(x) for x in input().split(' ')]
    storage[a] += b
    if a not in exist:
        exist.append(a)
exist.sort()
sum = 0
for i in exist:
    sum += storage[i]
    if sum >= k:
        print(i)
        break
    else:
        continue


### FIXED CODE ###

n, k = [int(x) for x in input().split(' ')]
exist = []
storage = [0 for x in range(10 ** 5+1)]
for i in range(n):
    a, b = [int(x) for x in input().split(' ')]
    storage[a] += b
sum = 0
for i in range(1, 10**5+1):
    sum += storage[i]
    if sum >= k:
        print(i)
        break
    else:
        continue
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

N, Q = map(int,input().split())
edge = [[] for i in range(N+1)]

for _ in range(N-1):
    a, b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

cnt = [0 for i in range(N+1)]

for i in range(Q):
    p, x = map(int,input().split())
    cnt[p] += x

def dfs(parent,i):
    for k in edge[i]:
        if k != parent:
            cnt[k] += cnt[i]
            dfs(i,k)
    return

dfs(-1,1)

ans = cnt[1:]

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(parent,i,add):
    for k in graph[i]:
        if k != parent:
            value[k] += add
            dfs(i,k,value[k])
    

dfs(0,1,value[1])

ans = value[1:]

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

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

s = input().splitlines()[0]
t = input()

Slen = len(s)
Index = -1
Loop = 0
LUT = [[] for i in range(26)]
Cur = [0 for i in range(26)]
for i, c in enumerate(s):
    v = ord(c) - ord('a')
    LUT[v].append(i)

NotFound = False
for c in t:
    v = ord(c) - ord('a')
    l = len(LUT[v])
    if l == 0:
        NotFound = True
        break
    if LUT[v][Cur[v]] > Index:
        Index = LUT[v][Cur[v]]
        Cur[v] += 1
        if Cur[v] >= l:
            Cur[v] = 0
    else:    
        Index = LUT[v][0]
        for i in range(26):
            Cur[i] = 0
            if len(LUT[i]) > 0:
                for j,k in enumerate(LUT[i]):
                    if k <= Index:
                        Cur[i] = j
        Loop += 1

if NotFound:
    print(-1)
else:
    print(Loop*Slen+Index+1)


### FIXED CODE ###

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


def main():
    s = input().splitlines()[0]
    t = input().splitlines()[0]

    Slen = len(s)

    LookupTable = [[] for i in range(26)]
    for i, c in enumerate(s):
        v = ord(c) - ord('a')
        LookupTable[v].append(i)
    for i in range(26):
        LookupTable[i].append(-1)
        
    IndexTable = [0 for i in range(26)]
    NextTable = []
    for i, c in enumerate(s):
        v = ord(c) - ord('a')
        NextTable.append( [LookupTable[k][IndexTable[k]] for k in range(26)] )
        IndexTable[v] += 1
        if LookupTable[v][IndexTable[v]] < 0:
            IndexTable[v] = 0

    Index = 0
    Loop = 0
    for i, c in enumerate(t):
        v = ord(c) - ord('a')
        if NextTable[Index][v] < Index:
            Loop += 1
        Index = NextTable[Index][v]
        if Index < 0:
            print(-1)
            return
        Index += 1
        if Index >= Slen:
            Index = 0
            Loop += 1

    print(Loop*Slen+Index)


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

s = list(input())
cnt = 0
ans = 0
while True:
    if 'W' not in s:
        break
    
    for i in range(len(s)):
        if s[i] == 'B':
            cnt += 1
        else:
            ans += cnt
            cnt = 0
            s.pop(i)
            break

print(ans)

### FIXED CODE ###

s = list(input())
cnt = 0
ans = 0
for i in range(len(s)):
    if s[i] == 'B':
        cnt += 1
    else:
        ans += cnt

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

import sys
import math
N = input()
AList = list(map(int, input().split()))
listnum = 1000000000

low = -1000000000
high = 1000000000

mode = 1
p = 0
a = 0
while(True):
    L = []
    center = math.floor((low + high)/2)
    for i in range(-1+center, 2+center):
        for j in range(1,int(N)+1):
            p += abs(AList[j-1] -(i + j))
        L.append(p)        
        p = 0

    if L[1] == min(L):
        print(L[1])
        sys.exit()
    elif L[0] == min(L):
        high = center - 1
    else:
        low = center + 1        

### FIXED CODE ###

from statistics import median
N = int(input())
AList = list(map(int, input().split()))
 
L = []
m = 0
for j in range(1, N+1):
    L.append(AList[j-1] - j)
m = median(L)
 
p = 0
for j in range(1, N+1):
    p += abs(AList[j-1] - j - m)
 
print(int(p))
### BUGGY CODE ###

import bisect
N = int(input())

c = []
for i in range(N):
    n = int(input())
    index = bisect.bisect_left(c,n)
    if index == 0:
        c.append(n)
    else:
        c[index-1] = n
    c.sort()
    #print(c)

print(len(c))      

### FIXED CODE ###

import bisect
N = int(input())

def bisect_right_reverse(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return hi


c = []
for i in range(N):
    n = int(input())
    index = bisect_right_reverse(c,n)
    #print(index)
    if index == len(c):
        c.append(n)
    else:
        c[index] = n
    #print(c)

print(len(c))
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def s_d(self, goal):
        return self.dist[goal]

xs, ys, xg, yg = list(map(int, input().split()))
xyr = []
xyr.append([xs, ys, 0])
N = int(input())

for i in range(N):
    xyr.append(list(map(int, input().split())))
xyr.append([xg, yg, 0])

g_a = Graph()
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        a, b = i, j
        R = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        if R > xyr[i][2] + xyr[j][2]:
            r = R - xyr[i][2] - xyr[j][2]
        else:
            r = 0
        g_a.add_edge(a, b, r)
        g_a.add_edge(b, a, r)

d_a = Dijkstra(g_a, 0)
print(d_a.s_d(N + 1))

### FIXED CODE ###

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

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))
        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def s_d(self, goal):
        return self.dist[goal]


xs, ys, xg, yg = list(map(int, input().split()))
xyr = []
xyr.append([xs, ys, 0])
N = int(input())

for i in range(N):
    xyr.append(list(map(int, input().split())))
xyr.append([xg, yg, 0])

g_a = Graph()
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        R = ((xyr[i][0] - xyr[j][0]) * (xyr[i][0] - xyr[j][0]) + (xyr[i][1] - xyr[j][1]) * (xyr[i][1] - xyr[j][1]))
        R = R ** 0.5
        if R > xyr[i][2] + xyr[j][2]:
            r = R - xyr[i][2] - xyr[j][2]
        else:
            r = 0
        g_a.add_edge(i, j, r)
        g_a.add_edge(j, i, r)

d_a = Dijkstra(g_a, 0)
print(d_a.s_d(N + 1))
### BUGGY CODE ###

n, m = map(int, input().split())
joblist = []
for _ in range(n):
    a, b = map(int, input().split())
    joblist.append([a, b])
joblist.sort()
ans = 0
p = 0
jobable = []
for i in range(1, m+1):
    for j in range(n):
        if joblist:
            if p == n:
                break
            if joblist[p][0] == i:
                jobable.append(joblist[p][1])
                p += 1
            else:
                break
        else:
            break
    if jobable:
        k = max(jobable)
        ans += k
        jobable.remove(k)
print(ans)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
work = [0]*n
for i in range(n):
  work[i] = list(map(int, input().split()))

work.sort()
k = 0
workable = []
heapq.heapify(workable)
ans = 0
for i in range(m):
  while k < n:
    if work[k][0] <= i+1:
      heapq.heappush(workable, -work[k][1])
      k += 1
    else:
      break
  if workable:
    ans += -heapq.heappop(workable)
print(ans)