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


H, W = list(map(int, input().split()))

maze = []
for _ in range(H):
    maze.append(list(input()))

def dfs(i, j, path):
    global ans
    if i == end[0] and j == end[1]:
        # print(path)
        ans = min(ans, path)
        return 

    for dx, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        x = i + dx
        y = j + dj
        if 0 <= x < H and 0 <= y < W and maze[x][y] == "." :
            if (x, y) not in seen:
                seen.add((x, y))
                dfs(x, y, path+1)
                seen.discard((x, y))   
    return

res = []
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                if maze[i][j] == "." and maze[k][j] == ".":
                    ans = float("inf")
                    seen = set()
                    seen.add((i, j))
                    end = (k, l)
                    dfs(i, j, 0)
                    if ans != float("inf"):
                        res.append(ans)
                    # res = max(res, ans if ans != float("inf") else 0)

print(max(res))


### FIXED CODE ###

from collections import deque

H, W = list(map(int, input().split()))

maze = []
for _ in range(H):
    maze.append(list(input()))

#bfsならうまく解ける!!
def bfs(i, j):
    q = deque([(i, j, 0)])
    seen = set([(i, j)])
    ans = 0
    while q:
        i, j, d = q.popleft()
        ans = max(ans ,d)
        for dx, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            x = i + dx
            y = j + dj
            if 0 <= x < H and 0 <= y < W and maze[x][y] == "." :
                if (x, y) not in seen:
                    seen.add((x, y))
                    q.append((x, y, d + 1))           
    return ans


res = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            res = max(res, bfs(i, j))
print(res)
### BUGGY CODE ###

a,b,n = map(int, input().split())
ans = 0
for i in range(n+1):
    c = a*i//b - a*(i//b)
    if ans > c:
        break
    ans = c
print(ans)


### FIXED CODE ###

a,b,n = map(int, input().split())
if b-1 < n:
    n = b-1
print(a*(n)//b - a*((n) // b))
### BUGGY CODE ###

MOD = 10 ** 9 + 7

s = str(input())

s = list(s)

cur = [0] * 13

if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1

for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            cur[(j * 10 + int(s[i])) % 13] = (cur[(j * 10 + int(s[i])) % 13] + pre[j]) % MOD
    else:
        for j in range(13):
            for k in range(10):
                cur[(j * 10 + k) % 13] =  (cur[(j * 10 + k) % 13]+ pre[j]) % MOD

print(cur[5] % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
 
s = str(input())
 
s = list(s)
 
cur = [0] * 13
 
if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1
 
for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD
 
print(cur[5] % MOD)
### BUGGY CODE ###

import sys


a = int(input())

if a % 2 == 0:
	print('-1')
	sys.exit()

n = 7
i = 0
for f in range(a):
	b = sum([(7 * (10**x)) for x in range(i + 1)])
	if b % a == 0:
		print(i + 1)
		sys.exit()
	else:
		i = i + 1

### FIXED CODE ###

import sys


a = int(input())

cur = 0
for i in range(1, 10 ** 7):
	#b = sum([(7 * (10**x)) for x in range(i + 1)])
    cur *= 10
    cur += 7
    cur %= a
    if cur == 0:
        print(i)
        sys.exit()
print(-1)
### BUGGY CODE ###

N=input()
S={"R":[],"G":[],"B":[]}
for i,s in enumerate(input()):
	S[s].append(i)

lis = [sorted([a, b, c]) for a in S["R"] for b in S["G"] for c in S["B"]]
ans = 0
for i,j,k in lis:
  if j-i!=k-j:
    ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()

ans = S.count("R")*S.count("G")*S.count("B")

for i in range(N):
	for j in range(N-i):
		if i+2*j>=N:
			break
		elif S[i]!=S[i+j] and S[i]!=S[i+2*j] and S[i+j]!=S[i+2*j]:
			ans-=1
print(ans)
### BUGGY CODE ###

n = int(input())

a_list = list(map(int, input().split()))
a_list.sort()
a_max = a_list[n-1]
temp_max = [1, 0]
bunbo = 1
bunshi = 1
candidate = []
a_set = set(a_list)
for i in range(a_max):
    if i == 0:
        continue
    bunbo *= max(1, i)
    bunshi *= max(1, a_max-i+1)
    if i in a_set:
        if bunshi//bunbo > temp_max[0]:
            temp_max = [bunshi//bunbo, i]

print(a_max, temp_max[1])


### FIXED CODE ###

n = int(input())

a_list = list(map(int, input().split()))
a_list.sort()
a_max = a_list[n - 1]
temp_max = [1, 0]
bunbo = 1
bunshi = 1
center = int((a_max + 1) / 2)
a_set = set(a_list)
diff_min = a_max
ans = 0
for a in a_set:
    diff = abs(a-center)
    if diff_min > diff:
        diff_min = diff
        ans = a

print(a_max, ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    XY = (tuple(map(int, input().split())) for _ in [0] * N)

    x = [0] * N
    y = [0] * N
    for i, (j, k) in enumerate(XY):
        x[i] = j
        y[i] = k

    ans = float('inf')
    for xi in range(N):
        for xj in range(N):
            for yi in range(N):
                for yj in range(N):
                    cnt = 0
                    for i in range(N):
                        if x[xi] <= x[i] <= x[xj] and y[yi] <= y[i] <= y[yj]:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, (x[xj] - x[xi]) * (y[yj] - y[yi]))

    print(ans)

main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    XY = (tuple(map(int, input().split())) for _ in [0] * N)

    x = [0] * N
    y = [0] * N
    for i, (j, k) in enumerate(XY):
        x[i] = j
        y[i] = k

    ans = float('inf')
    for xi in range(N):
        for xj in range(N):
            if x[xi] >= x[xj]: continue
            for yi in range(N):
                for yj in range(N):
                    if y[yi] >= y[yj]: continue
                    cnt = 0
                    for i in range(N):
                        if x[xi] <= x[i] <= x[xj] and y[yi] <= y[i] <= y[yj]:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, (x[xj] - x[xi]) * (y[yj] - y[yi]))

    print(ans)

main()
### BUGGY CODE ###

n = int(input())
List = list(input())
count = 0
for k in range(n - 2):
    for l in range(k + 1, n - 1):
        if List[k] != List[l]:
            for m in range(l + 1, min(2 * l - k, n)):
                if List[k] != List[m] and List[l] != List[m]:
                    count += 1
            for m in range(min(2 * l - k + 1, n), n):
                if List[k] != List[m] and List[l] != List[m]:
                    count += 1
print(count)

### FIXED CODE ###

n = int(input())
List = list(input())
count = List.count("R") * List.count("G") *List.count("B")
for w in range(1, n // 3 * 3 + 1):
    for s in range(n - 2 * w):
        if List[s] != List[s + w] and List[s] != List[s + w * 2] and List[s + w] != List[s + w * 2]:
            count -= 1
print(count)
### BUGGY CODE ###

from itertools import accumulate
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
T = [0, 0] + T + [0]
V = [0] + V + [0]
accT = list(accumulate(T))
INF = 10 ** 9

def speed(t, t0, t1, v):
    if t < t0:
        return (t0 - t) + v
    elif t > t1:
        return (t - t1) + v
    return v

ans = 0
sp_pre = 0
for t2 in range(0, accT[-1] * 2 + 1):
    t = t2 * 0.5
    sp = INF
    for t0, t1, v in zip(accT[:-1], accT[1:], V):
        sp = min(sp, speed(t, t0, t1, v))
    ans += 0.25 * (sp + sp_pre)
    sp_pre = sp

print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
T = [0, 0] + T + [0]
V = [0] + V + [0]
accT = np.cumsum(T)
INF = 10 ** 9

t2_max = accT[-1] * 2
speeds = np.ones(t2_max + 1) * INF
for t0, t1, v in zip(accT[:-1], accT[1:], V):
    sptmp = np.ones(t2_max + 1) * v
    sptmp[:t0 * 2] += np.arange(t0, 0, -0.5)
    sptmp[t1 * 2:] += np.arange(0, accT[-1] - t1 + 0.5, 0.5)
    speeds = np.minimum(speeds, sptmp)

ans = sum(speeds) / 2

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

import sys

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

if a == 0:
    print(0)
    sys.exit()

ans = 0
while n > 0:
    for i in range(a):
        ans += 1
        n -= 1
        if n <= 0: break
    n -= b
    
print(ans)

### FIXED CODE ###

import sys

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

if a == 0:
    print(0)
    sys.exit()

syou = n // (a+b)
amari = n % (a+b)

if amari <= a:
    print(syou*a + amari)
else:
    print(syou*a + a)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
l=[0]*q
for i in range(q):
    b,c=map(int,input().split())
    l[i]=(b,c)
book={}
for i in a:
    if i in book:
        book[i]+=1
    else:
        book[i]=1

for i in range(q):
    ans=0
    if l[i][0] in book:
        if l[i][1] in book:
            book[l[i][1]]+=book[l[i][0]]
            book[l[i][0]]=0
        else:
            book[l[i][1]]=book[l[i][0]]
            book[l[i][0]]=0
    for j in book:
        ans+=book[j]*j
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
l=[0]*q
ans=sum(a)
for i in range(q):
    b,c=map(int,input().split())
    l[i]=(b,c)
book={}
for i in a:
    if i in book:
        book[i]+=1
    else:
        book[i]=1

for i in range(q):
    if l[i][0] in book:
        if l[i][1] in book:
            ans+=(l[i][1]-l[i][0])*book[l[i][0]]
            book[l[i][1]]+=book[l[i][0]]
            book[l[i][0]]=0
        else:
            ans+=(l[i][1]-l[i][0])*book[l[i][0]]
            book[l[i][1]]=book[l[i][0]]
            book[l[i][0]]=0
    print(ans)
### BUGGY CODE ###

def find_divisors(n):
    divisors = []
    d = 2
    while n > 1:
        while n % d == 0:
            divisors.append(d)
            n //= d
        d += 1
    return divisors


if __name__ == '__main__':
    # ??????????????\???
    target_number = int(input())

    # ?¨?????????????
    results = find_divisors(target_number)

    # ???????????¨???
    print('{0}: {1}'.format(target_number, ' '.join(map(str, results))))

### FIXED CODE ###

def create_prime_list(limit):
    """ ??¨??????????????????????????§limit?????§????´???°?????????????±???????
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    # print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0] <= x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x % current_prime != 0]
    primes.extend(nums)
    # print(primes)
    return primes



def calc_divisors(n):
    """ n????????????????????¨?????§????????°????????? """
    if n in Primes:
        return [n]
    results = []
    i = 2
    start_num = n
    while n >= i**2:
        if n%i==0:
            while n%i==0:
                results.append(i)
                n //= i
            if n in Primes:
                results.append(n)
                n = 1
        i += 1
    #print('{0}????´???°: {1}'.format(start_num, results))
    if not results:
        results = [start_num]
    return results


Primes = set()
if __name__ == '__main__':
    # ??????????????\???
    target_number = int(input())
    # target_number = 999993031
    # target_number = 1463616



    # ?¨?????????????
    Primes = set(create_prime_list(int(10**4.5)+1))
    results = calc_divisors(target_number)

    # ???????????¨???
    print('{0}: {1}'.format(target_number, ' '.join(map(str, results))))
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
c=0
for i in range(n-1):
    for j in range(i+1,n):
        if A[i]+A[j]==j-i:
            c+=1
print(c)

### FIXED CODE ###

#j-i=Ai+Aj Ai+i=-Aj+j
#Li=Ai+i
#Ri=-Ai+i
#とおくと、Li=Rjとなるとき、Aiが正なので、必ずi<jとなる
from collections import defaultdict

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

L=defaultdict(int)
R=defaultdict(int)

for i in range(n):
	L[A[i]+i+1]+=1
	R[-A[i]+i+1]+=1

r=0
for k,v in L.items():
	j=R[k]
	r+=v*j

print(r)
### BUGGY CODE ###

#!/usr/bin/env python3


def main():
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7

    digit_0 = [0] * 60
    digit_1 = [0] * 60

    for i in range(N):
        for j in range(60):
            if (A[i] >> j) & 1:
                digit_1[j] += 1
            else:
                digit_0[j] += 1
    
    ans = 0
    for j in range(60):
        ans += ((digit_0[j] * digit_1[j] % p) * pow(2,j,p) % p)
        ans %= p
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3


def main():
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7

    digit_0 = [0] * 60
    digit_1 = [0] * 60

    for i in range(N):
        for j in range(60):
            if (A[i] >> j) & 1:
                digit_1[j] += 1
            else:
                digit_0[j] += 1
    
    ans = 0
    for j in range(60):
        ans += ((digit_0[j] * digit_1[j] % p) * pow(2,j,p) % p)
        ans %= p
    print(ans)

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

from collections import defaultdict
e=defaultdict(dict)

n=int(input())
a=[int(i) for i in input().split(" ")]
b=[int(i) for i in input().split(" ")]
c=[int(i) for i in input().split(" ")]

n=0
for i in a:
  n+=sum([len([k for k in c if k > j]) for j in b if j > i])
print(n)

### FIXED CODE ###

import bisect

n=int(input())
a=[int(i) for i in input().split(" ")]
b=[int(i) for i in input().split(" ")]
c=[int(i) for i in input().split(" ")]

a.sort()
c.sort()
lc=len(c)
print(sum([(lc-bisect.bisect_right(c,j))*(bisect.bisect_left(a,j)) for j in b]))
### BUGGY CODE ###

N,K = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]

L = []
for i in range(N):
    
    L += [ab[i][0]] * ab[i][1]
    
L.sort()
print(L[K-1])
    
    

### FIXED CODE ###

N,K = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]

ab.sort(key = lambda x:x[0])
idx = 0
i = 0
while True:
    if idx + ab[i][1] > K-1:
        ans = ab[i][0]
        break
    else:
        idx += ab[i][1]
    i += 1
    


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

inp = input().split()
n,k = map(int, inp)
nums = list(input().split())
nums_list = list(map(int, nums))
if len(nums_list) < k:
    print(0)
else:
    for i in range(k):
        nums_list.pop(nums_list.index(max(nums_list)))
    print(sum(nums_list))

### FIXED CODE ###

inp = input().split()
n,k = map(int, inp)
nums = list(input().split())
nums_list = list(map(int, nums))
kill_en_hp = 0
if len(nums_list) < k:
    print(0)
else:
    nums_list.sort(reverse=True)
    nums_list_2 = nums_list[k:]
    print(sum(nums_list_2))
### BUGGY CODE ###

from heapq import heappush, heappop
from copy import deepcopy

def main():
    n, m = map(int,input().split())
    
    h = []
    for i in range(n):
        day, value = map(int,input().split())
        heappush(h, (-1*value, day))
    
    res = 0
    done = []
    for i in range(1, m+1):
        cur_h = deepcopy(h)
        while cur_h:
            r = heappop(cur_h)
            if r[1] <= i and not r in done:
                res += r[0]*-1
                done.append(r)
                break

    print(res)

if __name__ == "__main__":
    main()
        



### FIXED CODE ###

from heapq import heappush, heappop
 
def main():
    n, m = map(int,input().split())
    
    jobs = []
    for i in range(n):
        day, value = map(int,input().split())
        jobs.append((day, value))

    jobs.sort()
    
    cur, res = 0, 0
    done = []
    h = []
    for i in range(1, m+1):
        while cur < n and jobs[cur][0] <= i:
            heappush(h, -jobs[cur][1])
            cur += 1
        if not h:
            continue
        res -= heappop(h)
 
    print(res)
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
def main():

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


    isprime = [True] * (1 + pow(10, 6))
    prime = []
    SPF = [None] *  (1 + pow(10, 6))
    def manipulated_seive(N):
        isprime[0] = isprime[1] = False
        for i in range(2, N):
            if isprime[i] == True:
                prime.append(i)
                SPF[i] = i
            j = 0
            while (j < len(prime) and i * prime[j] < N and prime[j] <= SPF[i]):

                isprime[i * prime[j]] = False
                SPF[i * prime[j]] = prime[j]

                j += 1
        return

    manipulated_seive(max(A))
    prime = set(prime)

    d = dict()
    ispair = True
    isset = True

    for v in A:
        for p in prime:
            if p <= v:
                if v % p == 0:
                    d[p] = d.get(p, 0) + 1
                    u = v // p
            else:
                break
    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import math
import collections
def main():

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

    def prime_factorize(n):
        a = []
        while n % 2 == 0:
            a.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.append(n)
        return a

    ispair = True
    isset = True

    d = dict()
    for v in A:
        for u in set(prime_factorize(v)):
            d[u] = d.get(u, 0) + 1
    # print(d)

    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

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

N = input()

data = map(int,raw_input().split())
data.sort()

ans = 0
i = 0
while i < N:
    count = data.count(data[i])
    if count < data[i]:
        ans += count
    else:
        ans += count-data[i]
    i += count;

print ans

### FIXED CODE ###

N = input()

data = map(int,raw_input().split())
data.sort()

count = []
num = []
pnum = -1
counter = -1

for i in data:
    if pnum != i:
        pnum = i
        num.append(i)
        count.append(1)
        counter += 1
    else:
        count[counter] += 1

ans = 0

for i in range(len(num)):
    if count[i] < num[i]:
        ans += count[i]
    else:
        ans += count[i]-num[i]

print ans
### BUGGY CODE ###

A, B, N = map(int,input().split())
score = 0
for i in range(int(N//1.1) ,N):
    x = i+1
    val = int(A*x/B) - A * int(x/B)
    #print( int(A*x/B) , A * int(x/B))
    if(val > score):
        score = val
print(score)


### FIXED CODE ###

A, B, N = map(int,input().split())
x = min(N,B-1)
val = int(A*x/B) - A * int(x/B)
print(val)
### BUGGY CODE ###

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

h = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]

cnt = 0

for i in range(1,n+1): # 1~nまでから1つ選ぶ
    num = h[i-1] # 選んだ展望台の高さをnumに格納
    flag = True
    for k in range(m): # 比較する要素を選ぶ
        if i == ab[k][0]:
            c = ab[k][1]
            if num <= h[c-1]:
                flag = False
                break
        elif i == ab[k][1]:
            c = ab[k][0]
            if num <= h[c-1]:
                flag = False
                break
    if flag == True:
        cnt +=1
print(cnt)


### FIXED CODE ###

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

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

l = [1]*n

for i in range(m):
    a,b = map(int, input().split())
    if h[a - 1] <= h[b - 1]:
        l[a - 1] = 0
    if h[b - 1] <= h[a - 1]:
        l[b - 1] = 0

print(sum(l))
### BUGGY CODE ###

import math
import heapq

def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    # 距離をinfで初期化
    d = [inf for i in range(n)]
    d[s] = 0

    # sへの距離は0
    q = [[0,s]]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば
    # p[1]から行ける
    while q:
        c,p = heapq.heappop(q)

        # 頂点p[1]までの距離がheapないのp[1]までの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点p[1]から伸びる、全ての辺の距離を確認
        for cost,to in path[p]:
            # 頂点p[1]から行ける頂点の距離がp[1]までの距離とp[1]からの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,[d[to], to])
    return d

xs,ys,xt,yt = map(int,input().split())
n = int(input())
barrier = [list(map(int, input().split())) for i in range(n)]

barrier = [[xs,ys,0]] + barrier + [[xt,yt,0]]
n+=2

path = [[] for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        length = max(math.sqrt((barrier[i][0]-barrier[j][0])**2 + (barrier[i][1]-barrier[j][1])**2)-barrier[i][2]-barrier[j][2],0)
        path[i].append([length,j])
        path[j].append([length,i])

d = dijkstra(0,path)

print(d[-1])

### FIXED CODE ###

import math
import heapq

def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    # 距離をinfで初期化
    d = [inf for i in range(n)]
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for cost,to in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d

xs,ys,xt,yt = map(int,input().split())
n = int(input())
barrier = [list(map(int, input().split())) for i in range(n)]

barrier = [[xs,ys,0]] + barrier + [[xt,yt,0]]
n+=2

path = [[] for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        length = max(math.sqrt((barrier[i][0]-barrier[j][0])**2 + (barrier[i][1]-barrier[j][1])**2)-barrier[i][2]-barrier[j][2],0)
        path[i].append([length,j])
        path[j].append([length,i])

d = dijkstra(0,path)

print(d[-1])
### BUGGY CODE ###

n = int(input())
s = []
count = 0

for i in range(n):
    tmp = input()
    if tmp not in s:
        count += 1
    s.append(tmp)

print(count)

### FIXED CODE ###

# よりシンプルな解答

n = int(input())
s = [input() for _ in range(n)]

print(len(set(s)))
### BUGGY CODE ###

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

for d in D:
    if d in T:
        T.remove(d)

if T:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

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

dictD = {}
for d in D:
    if d in dictD:
        dictD[d] += 1
    else:
        dictD[d] = 1

dictT = {}
for t in T:
    if t in dictT:
        dictT[t] += 1
    else:
        dictT[t] = 1


for k, v in dictT.items():
    if k in dictD:
        if v > dictD[k]:
            print("NO")
            exit()
    else:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

a,b = map(int,input().split())
ans = 0
if a > b:
  for x in range(b+1):
    if x > a:
      break
    for y in range(b-x+1):
      if y > a:
        break
      for z in range(b-x-y+1):
        if (x+y+z)==b:
          ans += 1
        if z > a:
          break
else:
  for x in range(a+1):
    for y in range(a+1):
      for z in range(a+1):
        if (x+y+z)==b:
          ans += 1
        if (x+y+z)>=b and (x>=b or y>=b or z>=b):
          break
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())
ans = 0

for x in range(b+1):
  if x > a:
    break
  for y in range(b+1):
    if y > a:
      break
    z = b-x-y
    if z <= a and z >= 0:
      ans +=1
    else:
      continue  
print(ans)