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

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = 0
c = 0
d = "Yes"
l = 1 / (4 * m)
for i in a:
  b += i
b = b * l
while c < m:
  if a[c] < b:
    d = "No"

print(d)


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
b = 0
c = 0
d = ""
l = 1 / (4 * m)
for i in a:
    b += i
b = b * l
while c < m:
  if a[c] < b:
    d = "No"
  else:
    d = "Yes"
  c += 1
print(d)
### BUGGY CODE ###

from itertools import product
def prime_factors(N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            t = 1
            while tmp%i == 0:
                tmp //= i
                t *= i
            ret.append(t)
    if tmp != 1:
        ret.append(tmp)
    return ret

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def main():
    N = int( input())
    P = prime_factors(2*N)
    M = len(P)
    ans = 2*N-1
    for p in product( range(2), repeat=M):
        x = 1
        for i, t in enumerate(p):
            if t == 1:
                x *= P[i]
        y = N*2//x
        if x == 1:
            if y-1 < ans:
                ans = y-1
            continue
        if y == 1:
            if x-1 < ans:
                ans = x-1
            continue
        _, a, b = xgcd(x,y)
        now = -a*x
        # print(x, y, a, b)
        if a < 0:
            pass
        else:
            now = -b*y
        if now < ans:
            ans = now
    print(ans)
        
        
if __name__ == '__main__':
    main()


### FIXED CODE ###

from itertools import product
def prime_factors(N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            t = 1
            while tmp%i == 0:
                tmp //= i
                t *= i
            ret.append(t)
    if tmp != 1:
        ret.append(tmp)
    return ret

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def main():
    N = int( input())
    # print("start")
    P = prime_factors(2*N)
    M = len(P)
    ans = 2*N-1
    # print(M)
    for p in product( range(2), repeat=M):
        x = 1
        for i, t in enumerate(p):
            if t == 1:
                x *= P[i]
        y = N*2//x
        if x == 1:
            if y-1 < ans:
                ans = y-1
            continue
        if y == 1:
            if x-1 < ans:
                ans = x-1
            continue
        _, a, b = xgcd(x,y)
        now = -a*x
        # print(x, y, a, b)
        if a < 0:
            pass
        else:
            now = -b*y
        if now < ans:
            ans = now
    print(ans)
        
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, k, q = map(int, input().split())
l = [int(input())-1 for _ in range(q)]
l.sort()
 
for i in range(n):
  cnt = 0
  if l and l[0] == i:
    while l and l[0] == i:
      l.pop(0)
      cnt += 1
  print(('No','Yes')[k > q - cnt])

### FIXED CODE ###

n, k, q = map(int, input().split())
l = [int(input())-1 for _ in range(q)]
l.sort()

for i in range(n):
  cnt = 0
  if l and l[0] == i:
    while l and l[0] == i:
      l.pop(0)
      cnt += 1
  print(('No','Yes')[k > q - cnt])
### BUGGY CODE ###

S = input()

idx = 0
pick = 0
while(("0" in S) and ("1" in S)):
#    print("S = " + S)
    if(S[idx] != S[idx + 1]):
#        print("idx = {} : S[:idx] = {}, S[idx + 2:] = {}, new str = {} ".format(idx, S[:idx], S[idx + 2:], S[:idx] + S[idx + 2:]))
        S = S[:idx] + S[idx + 2:]
        pick = pick + 2
    else:
        idx = idx + 1

    if(idx > len(S) - 2):
        idx = 0

print(pick)


### FIXED CODE ###

S = input()

cnt0 = 0
cnt1 = 0
for i in range(len(S)):
    if("0" == S[i]):
        cnt0 = cnt0 + 1
    else:
        cnt1 = cnt1 + 1

print(2 * min(cnt0, cnt1))
### BUGGY CODE ###

N=int(input())

c_list = []
for i in range(10):
    temp_list = []
    for j in range(10):
        temp_count = 0
        for n in range(1, N+1):
            if n%10==j and n//(10**(len(str(n))-1) )==i:
                temp_count += 1
        temp_list.append(temp_count)
    c_list.append(temp_list)
sum=0
for i in range(10):
    for j in range(10):
        sum += c_list[i][j]*c_list[j][i]
print(sum)


### FIXED CODE ###

N=int(input())

N_digit = len(str(N))
if N_digit==1:
    print(N)
    exit()

N_head = N//(10**(N_digit-1))
N_tail = N%10

count = 0
for A in range(1, N+1):
    A_digit = len(str(A))
    A_head  = A//(10**(A_digit-1))
    A_tail  = A%10

    if A_tail==0:
        continue

    if A_head==A_tail:
        count += 1

    for digit in range(2, N_digit+1):
        if digit==N_digit:
            if A_tail < N_head:
                count += 10**(digit-2)
            elif A_tail == N_head:
                if A_head <= N_tail:
                    count += N//10-N_head*(10**(N_digit-2))+1
                else:
                    count += N//10-N_head*(10**(N_digit-2))
            else:
                pass
        else:
            count += 10**(digit-2)
print(count)
### BUGGY CODE ###

import numpy as np

n = int(input())

a = [i for i in list(map(int, input().split()))]

for i in range(n):
  aa = a[:]
  aa.pop(i)
  ab=np.array(aa)
  num=0
  for j in set(aa):
    ns = len(ab[ab==j])
    if ns>1:
      num += (ns*(ns-1))//2

  print(num)

### FIXED CODE ###

import numpy as np

n = int(input())

a = np.array(list(map(int, input().split())))
d = [0] * (n+1)
s = {}

for i in a:
  d[i] += 1
  
sum = 0
for k in d:
  if k>1:
    sum += (k*(k-1))//2

for i in range(n):
  ans=sum-d[a[i]]+1
  print(ans)
### BUGGY CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        import time
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        t = time.time()
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        assert(time.time() - t <= 0.3)
        done = [0] * n
        self.cnt = 0
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                self.cnt += 1
                assert(self.cnt <= 10 ** 5 + 5)
                if rem <= 0:
                    return 0
                res *= rem * dfs(x, k - 2)
                res %= MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res = (res * rem) % MOD
                res = (res * dfs(x, k - 2)) % MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
L=[]
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        L.append(i+1)
n=len(L)
for i in range(Q):
    l,r=map(int,input().split())
    a=0
    for j in range(n):
        if l<=L[j]<r:
            a+=1
    print(a)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N,Q=map(int, input().split())
S=input()
L=[None]*(N)
t=0
for i in range(N-1):
    L[i]=t
    if S[i]=="A" and S[i+1]=="C":
        t+=1
L[-1]=t
for i in range(Q):
    l,r=map(int,input().split())
    print(L[r-1]-L[l-1])
### BUGGY CODE ###

#ABC077C
N=int(input())
#大きい順に並べる
A=sorted(list(map(int,input().split())), reverse=True)
B=sorted(list(map(int,input().split())), reverse=True)
C=sorted(list(map(int,input().split())), reverse=True)
#あるBの下にいくつCが入るか数える
C_under_B=[0]*N     #i番目のBの下に入るCの数
for i in range(N):
    # if j > 0:
    #     if B[i] == B[i-1]:
    #         C_under_B[i]=C_under_B[i-1]
    #         continue
    for j in range(N):
        if C[j]>B[i]:
            C_under_B[i]+=1
        else:       #C[j+1]>C[j]>B[i]なので検討を中止する
            break
#あるAの下にいくつBが入るか数える
B_under_A=[0]*N     #i番目のBの下に入るCの数
for i in range(N):
    # if j > 0:
    #     if A[i] == A[i-1]:
    #         B_under_A[i]=B_under_A[i-1]
    #         continue
    for j in range(N):
        if B[j]>A[i]:
            B_under_A[i]+=1
        else:       #B[j+1]>B[j]>A[i]なので検討を中止する
            break
#あるAのもとに入るBのもとに入るCを数える
C_under_B_under_A=[0]*N
for i in range(N):
    C_under_B_under_A[i]=sum([C_under_B[j] for j in range(B_under_A[i])])
#出力
print(sum(C_under_B_under_A))

### FIXED CODE ###

#ABC077C 解説を見て自作
import bisect
N=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
#あるBの下にいくつCが入るか数える
C_under_B=[0]*N     #i番目のBの下に入るCの数
for i in range(N):
    C_under_B[i]=N-bisect.bisect_right(C,B[i])
#あるBの上にいくつAが乗るか数える
A_on_B=[0]*N     #i番目のBの上に乗るAの数
for i in range(N):
    A_on_B[i]=bisect.bisect_left(A,B[i])
#あるBの上下におけるものを数えて出力
ans=0
for i in range(N):
    ans+=C_under_B[i]*A_on_B[i]
print(ans)
### BUGGY CODE ###

import heapq

xi = 0
yi = 0
zi = 0
def next(i):
    global xi, yi, zi, p, q, r
    if i == 0:
        xi += 1
        return heapq.nlargest(xi, p)[-1]
    elif i == 1:
        yi += 1
        return heapq.nlargest(yi, q)[-1]
    else:
        zi += 1
        return heapq.nlargest(zi, r)[-1]

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

ns = [next(0), next(1), next(2)]

val = 0

while x + y - xi - yi - zi + 3 > 0:
    if ns[0] >= ns[1] and ns[0] >= ns[2]:
        val += ns[0]
        if len(p) > 0 and x - xi > 0:
            ns[0] = next(0)
        else:
            xi += 1
            ns[0] = 0
    elif ns[0] <= ns[1] and ns[1] >= ns[2]:
        val += ns[1]
        if len(q) > 0 and y - yi > 0:
            ns[1] = next(1)
        else:
            yi += 1
            ns[1] = 0
    else:
        val += ns[2]
        if len(r) > 0:
            ns[2] = next(2)
        else:
            ns[2] = 0
print(val)


### FIXED CODE ###

import heapq

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p2 = heapq.nlargest(x, p)
q2 = heapq.nlargest(y, q)
r2 = heapq.nlargest(x+y, r)
p2.append(0)
q2.append(0)
r2.append(0)

pi = 0
qi = 0
ri = 0

val = 0

for _ in range(x+y):
    if p2[pi] >= q2[qi] and p2[pi] >= r2[ri]:
        val += p2[pi]
        pi += 1
    elif p2[pi] <= q2[qi] and q2[qi] >= r2[ri]:
        val += q2[qi]
        qi += 1
    else:
        val += r2[ri]
        ri += 1

print(val)
### BUGGY CODE ###

N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]

  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub == 0:
        dp[i + 1][j] += 2 ** (i) % 998244353
      if sub > 0 and dp[i][sub]:
        dp[i + 1][j] += dp[i][sub]
  #print(dp)
  print(dp[length][target] % 998244353)
  
solve(N, S, A)

### FIXED CODE ###

N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]
  dp[0][0] = 1
  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub >= 0:
        dp[i + 1][j] += dp[i][sub]
      dp[i + 1][j] %= 998244353
  #print(dp)
  print(dp[length][target])
  
solve(N, S, A)
### BUGGY CODE ###

def main():
  a = input()
  b = input()
  c = input()
  ab = [False]*20000
  ac = [False]*20000
  bc = [False]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  for i in range(-4000,4001,1):
    for j in range(-4000,4001,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
  
main()

### FIXED CODE ###

def main():
  a = input()
  b = input()
  c = input()
  ab = [None]*20000
  ac = [None]*20000
  bc = [None]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  AB = A+B
  AC = A+C
  for i in range(-AC,AC,1):
    for j in range(-AB,AB,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()
### BUGGY CODE ###

N = int(input())
L = [int(x) for x in input().split()]

import bisect
L = sorted(L)
ans = 0
for i in range(N - 2):
    for j in reversed(range(i + 2, N)):
        k = bisect.bisect_right(L[i+1:j], L[j] - L[i]) + i + 1
        ans += j - k
print(ans)

### FIXED CODE ###

N = int(input())
L = [int(x) for x in input().split()]

import bisect
L = sorted(L)
ans = 0
for i in range(N - 2):
    for j in reversed(range(i + 1, N - 1)):
        k = bisect.bisect_left(L, L[i] + L[j], j)
        ans += k - j - 1
print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
L=[0]*Q
P=[0]*Q
for i in range(Q):
	L[i],P[i]=map(int,input().split())
for i in range(Q):
	count=0
	D=S[L[i]-1:P[i]]
	for j in range(len(D)-1):
		if D[j]=="A":
			if D[j+1]=="C":
				count+=1
	print(count)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
X=[0]*N
for i in range(N-1):
	if S[i:i+2]=="AC":
		X[i+1]=X[i]+1
	else:
		X[i+1]=X[i]
for i in range(Q):
	L,R=map(int,input().split())
	print(X[R-1]-X[L-1])
### BUGGY CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(200000)


def main():
    def walk(p, c):
        if visited[p]:
            return
        visited[p] = True
        cnt[p] += c
        for n in tree[p]:
            walk(n, cnt[p])

    n, q = [int(x) for x in input().split()]

    tree = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = [int(x) for x in input().split()]
        tree[a].append(b)
        tree[b].append(a)

    cnt = [0] * (n + 1)
    for _ in range(q):
        p, x = [int(x) for x in input().split()]
        cnt[p] += x

    visited = [False] * (n + 1)
    walk(1, 0)

    print(*cnt[1:])


main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(1000000)


def main():
    def read_tree(n):
        parents = [0 for _ in range(n + 1)]
        for _ in range(n - 1):
            a, b = [int(x) for x in input().split()]
            parents[b] = a
        return parents

    n, q = [int(x) for x in input().split()]

    parents = read_tree(n)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = [int(x) for x in input().split()]
        cnt[p] += x
    
    for i in range(1, n + 1):
        cnt[i] += cnt[parents[i]]

    for i in range(1, n + 1):
        print(cnt[i], end=" ")


main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(len(a)):
  ans *= a[i]
if ans > 10**18:
  ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
  print(0)
  exit()
for i in range(len(a)):
  ans *= a[i]
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

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

mod=998244353

dp=[[0]*(k+1) for _ in range(n+1)]
dp[1][0]=m

for i in range(2,n+1):
    for j in range(k+1):
        dp[i][j]=((dp[i-1][j]*(m-1))%mod + dp[i-1][j-1]*(j!=0))%mod

ans=0
for j in range(k+1):
    ans+=dp[-1][j]
    ans%=mod
print(ans)

### FIXED CODE ###

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

mod=998244353

# 階乗計算
fact=[0]*(1+n)
fact[0]=1
for i in range(1,n+1):
    fact[i]=fact[i-1]*i % mod
    
# 階乗の逆元計算
invfact=[0]*(1+n)
invfact[-1]=pow(fact[-1],mod-2,mod) # 逆元を計算するのは最後の要素だけでよくてあとは、前に戻りながらかけていく。
for i in range(n-1,-1,-1):
    invfact[i]=invfact[i+1]*(i+1) % mod
    

# 二項係数のリスト化
def cmb(n,r,mod):
    if r<0 or n<r:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod
    
ans=0
for i in range(k+1):
    ans+=(cmb(n-1,i,mod)*m*pow(m-1,n-i-1,mod))%mod
    ans%mod
print(ans%mod)
### BUGGY CODE ###

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

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

import numpy as np
#import math
from fractions import gcd

def main():

    ##get int
    first_input = list(map(lambda x:int(x), input().split(" ")))
    #second_input = list(map(lambda x:int(x), input().split(" ")))

    ##get float
    #first_input = list(map(lambda x:float(x), input().split(" ")))
    #second_input = list(map(lambda x:float(x), input().split(" ")))

    ##get string
    #first_input = input().split(" ")

    K = first_input[0]

    gcd_sum = 0
    for a in range(1,K+1):
        for b in range(1,K+1):
            for c in range(1,K+1):
                gcd_sum = gcd_sum + gcd(gcd(a,b),c)

    print(gcd_sum)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#import numpy as np
import math
#from fractions import gcd

def main():

    ##get int
    first_input = list(map(lambda x:int(x), input().split(" ")))
    #second_input = list(map(lambda x:int(x), input().split(" ")))

    ##get float
    #first_input = list(map(lambda x:float(x), input().split(" ")))
    #second_input = list(map(lambda x:float(x), input().split(" ")))

    ##get string
    #first_input = input().split(" ")

    K = first_input[0]

    gcd_sum = 0
    for a in range(1,K+1):
        for b in range(1,K+1):
            for c in range(1,K+1):
                gcd_sum = gcd_sum + math.gcd(math.gcd(a,b),c)

    print(gcd_sum)

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

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

ans = 0
for n in range(1000):
    n = str(n).zfill(3)
    i = 0
    for j in range(N):
        if S[j] == n[i]:
            i += 1
            if i == 3:
                ans += 1
                break

print(ans)


### FIXED CODE ###

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

ans = 0
for n in range(1000):
    n = str(n).zfill(3)
    i = 0
    for j in range(N):
        if S[j] == n[i]:
            i += 1
            if i == 3:
                ans += 1
                break

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

from collections import deque
h, w = map(int, input().split())
C = [list(input()) for _ in range(h)]
# '#'の地点をスタートとしてqueに全部入れる
# その際にseenもかねたdist配列を-1で初期化して，スタート地点だけ0にする，（-1のところは未踏）
# タプルでqueに入れると少し早くなるらしい
que = deque()
dist = [[-1] * w for _ in range(h)]
for y in range(h):
    for x in range(w):
        if C[y][x] == '#':
            que.append((y, x))
            dist[y][x] = 0

while len(que) > 0:
    # 現在地点の座標と距離を取得
    now_y, now_x = que.popleft()
    now_d = dist[now_y][now_x]
    for dy, dx in ((1,0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1:
                # もしまだ見ていない地点ならqueに追加し，distを現在の距離+1に更新する
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_d + 1

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, dist[y][x])

print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
C = [list(input()) for _ in range(h)]
# '#'の地点をスタートとしてqueに全部入れる
# その際にseenもかねたdist配列を-1で初期化して，スタート地点だけ0にする，（-1のところは未踏）
# タプルでqueに入れると少し早くなるらしい
que = deque()
dist = [[-1] * w for _ in range(h)]
for y in range(h):
    for x in range(w):
        if C[y][x] == '#':
            que.append((y, x))
            dist[y][x] = 0

while len(que) > 0:
    # 現在地点の座標と距離を取得
    now_y, now_x = que.popleft()
    now_d = dist[now_y][now_x]
    for dy, dx in ((1,0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1:
                # もしまだ見ていない地点ならqueに追加し，distを現在の距離+1に更新する
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_d + 1

print(now_d)
### BUGGY CODE ###

ans=[]
n=int(input())
for nn in range(1,n+1):
  aa=0
  for i in range(1,101):
    for j in range(i,101):
      for k in range(j,101):
        if (i+j+k)**2-(i*j+j*k+k*i)==nn:
          ll=len(set([i,j,k]))
          if ll==1:
            aa+=1
          elif ll==2:
            aa+=3
          else:
            aa+=6
          break
  ans.append(aa)
for aa in ans:
  print(aa)

### FIXED CODE ###

n=int(input())
ans=[0]*n

for i in range(1,101):
  for j in range(i,101):
    for k in range(j,101):
      if 1<=(i+j+k)**2-(i*j+j*k+k*i)<=n:
        ll=len(set([i,j,k]))
        if ll==1:
          aa=1
        elif ll==2:
          aa=3
        else:
          aa=6
        ans[(i+j+k)**2-(i*j+j*k+k*i)-1]+=aa
for aa in ans:
  print(aa)
### BUGGY CODE ###

n,k=map(int,input().split())
s=input()
li=[]
seq=1
for i in range(1,len(s)):
    if s[i-1]==s[i]:
        seq+=1
    else:
        li.append(seq)
        seq=1
        
li.append(seq)


for i in range(k):
    if len(li)>=3:
        tmp=li[0]+li[1]+li[2]
        del li[0:3]
        li.insert(0,tmp)
    elif len(li)==2:
        tmp=li[0]+li[1]
        del li[0:2]
        li.insert(0,tmp)
    elif len(li)==1:
        break

print(sum(list(map(lambda x:x-1, li))))


### FIXED CODE ###

n,k=map(int,input().split())
s=input()
li=[]
seq=1
for i in range(1,len(s)):
    if s[i-1]==s[i]:
        seq+=1
    else:
        li.append(seq)
        seq=1
        
li.append(seq)
length=len(li)
ans=sum(li)-length

for i in range(k):
    if length>=3:
        length+=-2
        ans+=2
    elif length==2:
        ans+=1
        length+=-1
    else:
        break


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

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0

for a in range(len(L)):
    for b in range(a+1, len(L)):
        ans += bisect.bisect_left(L[b+1:], L[a]+L[b])
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0

for a in range(N-2):
    for b in range(a+1, N-1):
        ans += bisect.bisect_left(L, L[a]+L[b]) - (b+1)
print(ans)