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

n = int(input())
a = list(map(int,input().split()))
memo = {}
p = [0]
for num in a:
    p += [p[-1] + num]

dp = [[0 for _ in range(n)] for _ in range(n)]
for l in range(2,n+1):
    for i in range(n-l+1):
        dp[i][i+l-1] = min([dp[i][k] + dp[k+1][i+l-1] for k in range(i,i+l-1)]) + p[i+l] - p[i]
print(dp[0][n-1])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n+1) for _ in range(n+1)]
s = [0] * (n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]
for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        dp[i][j] = s[j] - s[i] + min(dp[i][k] + dp[k][j] for k in range(i+1, j))
print(dp[0][n])
### BUGGY CODE ###

N, X, Y = map(int, input().split())

X -= 1
Y -= 1

print(N)

def disdance(i, j):
    if i <= X and j >= Y:
        return X - i + j - Y + 1
    elif i >= X and j <= Y:
        return min(j - i, i - X + Y - j + 1)
    elif i >= X and j >= Y:
        return min(j - i, i - X + j - Y + 1)
    elif i <= X and j <= Y:
        return min(j - i, X - i + Y - j + 1)

d = []

for i in range(N - 1):
    for j in range(i + 1, N):
        d.append(disdance(i, j))

for k in range(2, N):
    print(d.count(k))

### FIXED CODE ###

N, X, Y = map(int, input().split())

print(N)

X -= 1
Y -= 1

def disdance(i, j):
    if i <= X and j >= Y:
        return X - i + j - Y + 1
    elif i >= X and j <= Y:
        return min(j - i, i - X + Y - j + 1)
    elif i >= X and j >= Y:
        return min(j - i, i - X + j - Y + 1)
    elif i <= X and j <= Y:
        return min(j - i, X - i + Y - j + 1)

d = [0] * N

for i in range(N - 1):
    for j in range(i + 1, N):
        d[disdance(i, j)] += 1

for k in range(2, N):
    print(d[k])
### BUGGY CODE ###

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

m = 0
import numpy as np
p = np.array(p)
for i in range(k):
  m += np.hstack([p[i:], np.zeros(i)])  

print((max(m)+k)/2)

### FIXED CODE ###

import itertools

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

pa = list(itertools.accumulate([0] + p))

m = 0
for i in range(n-k+1):
  s = pa[i+k] - pa[i]
  if s > m:
    m = s
print((m+k)/2)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    # dp[i][w][超えたか超えてないか超えたら1]:= (i番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値,[index])

    dp  = [[[0,[]] for _ in range(T)] for _ in range(N+1)]

    for i in range(N):
        for j in range(0,T):
            if j >= A[i]: ##今回の商品がjよりも小さい
                if dp[i][j-A[i]][0]+B[i]>=dp[i][j][0]: ## 選ぶ
                    dp[i+1][j][0] = dp[i][j-A[i]][0]+B[i]
                    dp[i+1][j][1] = dp[i][j-A[i]][1]+[i]
                else:
                    dp[i+1][j]= dp[i][j]
            else: ## 選ばない
                dp[i+1][j] = dp[i][j]
    
    index = list(range(0,N))
    a = list(set(index)- set(dp[N][T-1][1]))
    
    max_add = 0
    for i in a:
        max_add = max(max_add,B[i]) 

    print(dp[N][T-1][0]+max_add)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    # dp[i][w][超えたか超えてないか超えたら1]:= (i番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値,[index])

    AB = list(zip(A,B))
    AB.sort(key=lambda x:x[0])
    A = [AB[i][0] for i in range(N)]
    B = [AB[i][1] for i in range(N)]

    dp  = [[0 for _ in range(T)] for _ in range(N+1)]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][T-1]+B[i])

        for j in range(0,T):

            if j >= A[i]: ##今回の商品がjよりも小さい
                dp[i+1][j] = max(dp[i][j-A[i]]+B[i],dp[i][j])
            else: ## 選ばない
                dp[i+1][j] = dp[i][j]
             
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

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

from collections import defaultdict
n=int(input())
dic=defaultdict(int)
for _ in range(n):
	s=list(input())
	s.sort()
	s=''.join(s)
	dic[s]+=1
	ans=0
	for (k,v) in dic.items():
		ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
n=int(input())
dic=defaultdict(int)
for _ in range(n):
	s=list(input())
	s.sort()
	s=''.join(s)
	dic[s]+=1
ans=0
for (k,v) in dic.items():
	ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

K = int(input())

if K%2==0:
    print(-1)

r = 1
N = 0

while True:
    N += 7*(10**(r-1))
    if N%K ==0:
        break
    r += 1

print(r)


### FIXED CODE ###

K = int(input())

for i in range(K):
    if i == 0:
        N= 7%K
    else:
        N = (10*N+7)%K
    if N == 0:
        print(i+1)
        break
else:
    print(-1)
### BUGGY CODE ###

### a<=b<=cととることとし、a,bを固定すると
### cは　c<a+b
N = int(input())
lst = list(map(int, input().split()))
sor = sorted(lst)

def BinarySearch(lst, key): ## lstの値のうち、key以上になる最初のインデックス
    left = -1  ## index=0が条件を満たす場合も存在
    right = len(lst)  ## index = len(lst)-1が条件を満たさないこともある、key以上になるものが存在しない
    
    while right != left + 1:
        mid = (left + right) // 2
        val = lst[mid]
        if val >= key:
            right = mid
        elif val < key:
            left = mid
    return right  ### key以上になるものが存在しない場合はlen(lst)が帰る

res = 0
for i in range(N):
    for j in range(i+1, N):##ここでa<=bを満たしている
        a = sor[i]
        b = sor[j]
        ab = a+b

        highbound = BinarySearch(sor, ab)
        res += highbound - j - 1
print(res)

### FIXED CODE ###

### a<=b<=cととることとし、a,bを固定すると
### cは　c<a+b
N = int(input())
lst = list(map(int, input().split()))
sor = sorted(lst)

def BinarySearch(lst, key): ## lstの値のうち、key以上になる最初のインデックス
    left = -1  ## index=0が条件を満たす場合も存在
    right = len(lst)  ## index = len(lst)-1が条件を満たさないこともある、key以上になるものが存在しない
    
    while right != left + 1:
        mid = (left + right) // 2
        val = lst[mid]
        if val >= key:
            right = mid
        elif val < key:
            left = mid
    return right  ### key以上になるものが存在しない場合はlen(lst)が帰る

res = 0
for i in range(N):
    for j in range(i+1, N):##ここでa<=bを満たしている
        a = sor[i]
        b = sor[j]
        ab = a+b

        highbound = BinarySearch(sor, ab)
        res += highbound - j - 1
print(res)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z == s:
        count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0

for x in range(k+1):
  for y in range(k+1):
    if 0 <= s-(x+y) <= k:
      count += 1

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

from collections import defaultdict
import sys
import copy
sys.setrecursionlimit(10**6)

def readInput():
	return [int(i) for i in input().split(" ")]

(R, C) = readInput()
N = int(input())
rowIdx = set() 
cover = set()
grid = defaultdict(lambda:None)
rowGrid = defaultdict(set)
for i in range(N):
	(r, c, a) = readInput()
	r -= 1
	c -= 1
	rowGrid[r].add(c)
	grid[(r, c)] = a 
	rowIdx.add(r)

pairIdx = copy.copy(rowIdx)	
for i in rowIdx:
	tempRow = rowGrid[i]
	tempRow.difference_update(cover)
	if (len(tempRow) is 0):
		continue
	pairIdx.remove(i)
	for j in pairIdx:
		tempPair = rowGrid[j]
		mark = 1
		for k in tempRow:
			if (grid[(j, k)] is not None):
				diff = grid[(i, k)] - grid[(j, k)]
				mark = 0 
				break
		if (mark is 1):
			continue
		for m in tempRow:
			anchor = grid[(i, m)]
			anchorP = grid[(j, m)]
			if (anchorP is None and anchor < diff):
				print('No')
				exit()
			elif (anchorP is not None and anchor - anchorP != diff):
				print('No')
				exit()
		for n in tempPair:
			anchor = grid[(j, n)]
			anchorP = grid[(i, n)]
			if (anchorP is None and anchor < -diff):
				print('No')
				exit()
	cover &= tempRow
	if (len(cover) is C):
		break
print('Yes')

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))

n,k = inL()
a = inL()
sum = 1
sum2 = 1
for i in range(k):
    sum2 *= a[i]
for i in range(k,n):
    #print(sum2)
    sum = sum2 * a[i] / a[i-k] 
    if sum > sum2:
        print('Yes')
    else:
        print('No')
    sum2 = sum

### FIXED CODE ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))

n,k = inL()
a = inL()

for i in range(k,n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import fractions
from functools import reduce

import copy

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

ans = 1

for i in range(n):
  m = copy.copy(l)
  m.pop(i)
  if gcd_list(m) > ans:
    ans = gcd_list(m)

print(ans)
  

### FIXED CODE ###

import fractions

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

gcd_l = [0]
gcd_r = [0]

for i in range(n):
  gcd_l.append(fractions.gcd(gcd_l[i], l[i]))
  gcd_r.append(fractions.gcd(gcd_r[i], l[-(i+1)]))
gcd_r = gcd_r[::-1]
# print(gcd_l)
# print(gcd_r)

ans = [0]*n
for i in range(n):
  ans[i] = fractions.gcd(gcd_l[i], gcd_r[i+1])
print(max(ans))
### BUGGY CODE ###

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

for v in range(a, b+1):
    if v - a < k or b - v < k:
        print(v)

### FIXED CODE ###

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

if b - a < 2 * k:
    for v in range(a, b+1):
        print(v)
else:
    for v in range(a, a+k):
        print(v)
    for v in range(b-k+1, b+1):
        print(v)
### BUGGY CODE ###

import bisect

n=int(input())
a=[int(input()) for i in range(n)]

c=0
b=[]
for i in range(n):
  p=bisect.bisect_left(b,a[i])
  if p==0:
    b.append(a[i])
    c += 1
  else:
    b[p-1]=a[i]
  b.sort()

print(c)


### FIXED CODE ###

import bisect

N=int(input())
A=[-int(input()) for i in range(N)]

B=[]
c=0
for a in A:
  p=bisect.bisect_right(B,a)
  if p==c:
    B.append(a)
    c += 1
  else:
    B[p]=a

print(len(B))
### BUGGY CODE ###

N,K = input().split()
H = input().split()

for i in range(int(K)):
    if len(H) == 0:
        break

    H.pop(H.index(max(H)))

H = [int(i) for i in H]

print(sum(H))

### FIXED CODE ###

enemmyCountN,killerTimeK = map(int,input().split())
enemyHp = list(map(int,input().split()))

enemyHp.sort()

resultEnemyCount = enemmyCountN - killerTimeK
countNormal = 0

if killerTimeK >= enemmyCountN:
    print(0)

else:
    for i in range(resultEnemyCount):
        countNormal += enemyHp[i]
    print(countNormal)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    MAX = 10 ** 5 + 10
    k = [0] * MAX
    # v = [0] * MAX

    for a in A:
        k[a] += 1

    # print(k[:10])

    for i in range(Q):
        ans = 0
        b, c = map(int, input().split())
        if k[b] > 0:
            k[c] += k[b]
            k[b] = 0
        for i in range(MAX):
            ans += i * k[i]
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    d = Counter(A)
    # print(d)
    ans = sum(A)

    for i in range(Q):
        b, c = map(int, input().split())
        if d[b] != 0:
            ans -= d[b] * b
            ans -= d[c] * c
            d[c] += d[b]
            d[b] = 0
            ans += d[c] * c

        print(ans)


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

N, K = map(int, input().split())
S = list(input()) + ['2']

blocks = []
cur = 1
seq = 0
for s in S:
    if int(s) == cur:
        seq += 1
    else:
        blocks.append(seq)
        cur = 1 - cur
        seq = 1
answer = 0
for i in range(0, len(blocks), 2):
    answer = max(answer, sum(blocks[i:i+2*K+1]))
print(answer)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
S = np.array([int(x) for x in input()] + [2])

blocks = [] # 同じ数の塊
seq = 1
for i in range(N):
    if S[i+1] == S[i]:
        seq += 1
    else:
        blocks.append(seq)
        seq = 1
blocks = np.array(blocks)

answer = blocks[:2*K].sum()

start = 0 if S[0] == 1 else 1
for i in range(start, len(blocks), 2):
    answer = max(answer, blocks[i:i+(2*K+1)].sum())

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

n, m = map(int, input().split())
a = [0] + [int(input()) for _ in range(m)]

dp = [0] * (n + 1)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
MOD = 10 ** 9 + 7

for i in range(2, n + 1):
    if i in a:
        continue
    dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= MOD

print(dp[-1])


### FIXED CODE ###

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

mod=10**9+7

oks = [True]*(n+1)
for i in range(m):
    oks[a[i]] = False

dp=[0]*(n+1)
dp[0]=1
for now in range(0,n):
    for nex in range(now+1,min(n,now+2)+1):
        if oks[nex]:
            dp[nex]+=dp[now]
            dp[nex]%=mod
print(dp[n])
### BUGGY CODE ###

def main():
    N = str(input())
    count = 0
    for i in range(1, len(N)):
        target = N[i]
        if target == 'W':
            for j in range(0, i):
                if N[j] == 'B':
                    count = count + 1
    print(count)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = str(input())
    B_count = 0
    result = 0
    for i in range(0, len(N)):
        target = N[i]
        if target == 'W':
            result = result + B_count
        else:
            B_count = B_count + 1        
    print(result)

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

# 配るDP
N,K= map(int,input().split())
h_list = list(map(int,input().split()))
INF = 10**9 + 7
DP = [INF]*N
DP[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i+k >= N:
            continue
        DP[i+k] = min(DP[i+k],DP[i]+abs(h_list[i]-h_list[i+k]))  
print(DP[-1])



### FIXED CODE ###

# 配るDP
N,K= map(int,input().split())
h_list = list(map(int,input().split()))
INF = 10**9 + 7
DP = [INF]*N
DP[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i+k >= N:
            continue
        DP[i+k] = min(DP[i+k],DP[i]+abs(h_list[i]-h_list[i+k]))  
print(DP[-1])
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    A= list(map(int,input().split()))
    A = sorted(A)

    for i in range(M):
        B,C = map(int,input().split())

        index = bisect.bisect_right(A,C)

        if index > B:
            A = A[B:index] + [C] *B + A[index:]
        else:
            A = [C]*index + A[index:]
    print(sum(A))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N,M = map(int,input().split())
    A= list(map(int,input().split()))
    A = sorted(A)

    BC=[list(map(int,input().split())) for i in range(M)]
    BC = sorted(BC, key=lambda x: x[1],reverse=True)
    index=0
    max_index=len(A)
    
    for B,C in BC:
        temp = [C]*B
        for t in temp:
            if max_index>index and  t>A[index]:
                A[index] = t
            else:
                return A
            index+=1
    return A
    
if __name__ == '__main__':
    A=main()
    print(sum(A))
### BUGGY CODE ###

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

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

ans_list = []

for i in range(int(b / 1000000), n + 1):
  #print(int((a * i) / b), a * int(i / b), int((a * i) / b) - a * int(i / b))
  ans = int((a * i) / b) - a * int(i / b)
  ans_list.append(ans)
print(max(ans_list))



### FIXED CODE ###

# -*- coding: utf-8 -*-
# x = p * b + q
# 0 <= q < b
# int(a * p + a * q / b) - a * int(p - q / b)
# = a * p + int(a * q / b) - a * p
# = int(a * q / b)

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

print(a * min(b - 1, n) //  b)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


# Priority QueueとしてHeapを使う
# Pythonのheapqは小さい順に取り出すので、-1を掛けて負数としてpushしていく
#   (-Ai-Bj-Ck, i, j, k)
# 取り出したi, j, kについて、(i+1, j, k), (i, j+1, k), (i, j, k+1)に対応するタプルをpushする
# ただし、すでにpushした値は入れないようにする

import heapq



def make(i, j, k):
    return (-A[i]-B[j]-C[k], i, j, k)

# class flags:
#     def __init__(self, X, Y, Z):
#         self.ar = []
#         for k in range(X):
#             l = []
#             for j in range(Y):
#                 ll = []
#                 for i in range(Z):
#                     ll.append(False)
#                 l.append(ll)
#             self.ar.append(l)
        
#     def __getitem__(self, item):
#         return self.ar[item[0]][item[1]][item[2]]
    
#     def __setitem__(self, item, value):
#         self.ar[item[0]][item[1]][item[2]] = value
        

used = [[[False] * Z for i in range(Y)] for j in range(X)]

def push_next(l, i, j, k):
    if i < X - 1 and not used[i+1][j][k]:
        heapq.heappush(l, make(i+1, j, k))
        used[i+1][j][k] = True
    
    if j < Y - 1 and not used[i][j+1][k]:
        heapq.heappush(l, make(i, j+1, k))
        used[i][j+1][k] = True
    
    if k < Z - 1 and not used[i][j][k+1]:
        heapq.heappush(l, make(i, j, k+1))
        used[i][j][k+1] = True



l = []

heapq.heappush(l, make(0, 0, 0))
used[0][0][0] = True

for cnt in range(K):
    V, i, j, k = heapq.heappop(l)
    push_next(l, i, j, k)
    
    print(-V)




### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


# Priority QueueとしてHeapを使う
# Pythonのheapqは小さい順に取り出すので、-1を掛けて負数としてpushしていく
#   (-Ai-Bj-Ck, i, j, k)
# 取り出したi, j, kについて、(i+1, j, k), (i, j+1, k), (i, j, k+1)に対応するタプルをpushする
# ただし、すでにpushした値は入れないようにする

import heapq

def make(i, j, k):
    return (-A[i]-B[j]-C[k], i, j, k)


used = set()
l = []

heapq.heappush(l, make(0, 0, 0))
used.add((0, 0, 0))

for cnt in range(K):
    V, i, j, k = heapq.heappop(l)
    
    if i < X - 1 and (i+1, j, k) not in used:
        heapq.heappush(l, make(i+1, j, k))
        used.add((i+1, j, k))
    
    if j < Y - 1 and (i, j+1, k) not in used:
        heapq.heappush(l, make(i, j+1, k))
        used.add((i, j+1, k))
    
    if k < Z - 1 and (i, j, k+1) not in used:
        heapq.heappush(l, make(i, j, k+1))
        used.add((i, j, k+1))
    
    print(-V)
### BUGGY CODE ###

from collections import deque

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

B = []
for i,a in enumerate(A):
    for j,b in enumerate(a):
        if b == "#":
            B.append((i,j))
            
dxy = [[1,0],[-1,0],[0,1],[0,-1]]

stack = deque(B) # はじめの"#"の位置
darked = len(stack) # はじめの"#"の数
targetd = h*w
count = 0

while darked < targetd:
    nextd = deque([])
    
    while stack:
        x, y = stack.popleft()
        for dx,dy in dxy:
            X = x + dx
            Y = y + dy
            if not(0 <= X < h) or not(0 <= Y < w):
                continue
            if A[X][Y]==".":
                A[X][Y]="#"
                nextd.append((X,Y))
    count += 1
    stack = nextd
    darked += len(stack)
print(count)

### FIXED CODE ###

from collections import deque

def main():
    h, w = map(int,input().split())
    A = [list(input()) for _ in range(h)]
    B = []

    for i,a in enumerate(A):
        for j,b in enumerate(a):
            if b == "#":
                B.append((i,j))

    dxy = [[1,0],[-1,0],[0,1],[0,-1]]

    stack = deque(B)
    darked = len(stack)
    targetd = h*w
    count = 0

    while darked < targetd:
        nextd = deque([])

        while stack:
            x, y = stack.popleft()
            for dx,dy in dxy:
                X = x + dx
                Y = y + dy
                if not(0 <= X < h) or not(0 <= Y < w):
                    continue
                if A[X][Y]==".":
                    A[X][Y]="#"
                    nextd.append((X,Y))
        count += 1
        stack = nextd
        darked += len(stack)
    print(count)
    
main()
### BUGGY CODE ###

import sys
if sys.platform == 'ios':
	sys.stdin = open('input.txt')


n,q = map(int,input().split())
s = input()
l = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
	print(s[l[i][0]-1:l[i][1]].count('AC'))

### FIXED CODE ###

import sys
if sys.platform =='ios':
	sys.stdin=open('input.txt')

n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for _ in range(q)]

AC=[]
for i in range(n-1):
    if s[i]=="A":
        if s[i+1]=="C":
            AC.append(i)
#print(AC)

from bisect import bisect_right as br
from bisect import bisect_left as bl
for i in range(q):
    a=bl(AC,lr[i][0]-1)
    #print(i,AC,lr[i][0],a)
    b=br(AC,lr[i][1]-2)
    #print(a,b)
    print(b-a)
### BUGGY CODE ###

N,K = map( int, input().split() )
H = list( map( int, input().split() ) )
dp = [float("inf")]*N
dp[0] = 0
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 ###


def solve(K, S):
    import bisect
    count = 0
    z_array = [i for i in range(K+1)]
    for x in range(K+1):
        for y in range(K+1):
                z = S - x - y
                index = bisect.bisect_left(z_array, z)
                if(index != K+1 and z_array[index] == z):count+=1
    return count

def main():
    K, S = map(int, input().split())
    print(solve(K, S))
#print(solve(2, 2))
#print(solve(5, 15))
main()

### FIXED CODE ###


def solve(K, S):
    import bisect
    count = 0
    z_array = [i for i in range(K+1)]
    for x in range(K+1):
        for y in range(K+1):
                z = S - x - y
                if(z >= 0 and z <= K):count+=1
    return count

def main():
    K, S = map(int, input().split())
    print(solve(K, S))
#print(solve(2, 2))
#print(solve(5, 15))
main()
### BUGGY CODE ###

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

L.sort(reverse=True)

ans=0
for i in range(N):
  for j in range(i+1,N):
    if L[i]>=2*L[j]:
      break
    for k in range(j+1,N):
      if L[i]<L[j]+L[k]:
        ans+=1
      else:
        break
print(ans)

### FIXED CODE ###

import bisect

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

L.sort()
#print(L)

ans=0
for i in range(N-1,-1,-1):
  for j in range(i-1,-1,-1):
    if L[i]>=2*L[j]:
      break
    #print(L[i],L[j],bisect.bisect(L,L[i]-L[j]),j-bisect.bisect(L,L[i]-L[j]))
    ans+=j-bisect.bisect(L,L[i]-L[j])
print(ans)