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

import sys
import math
h, n = map(int, input().split())
INF = 10 ** 20
masics = []
for i in range(n):
  a, b = map(int, input().split())
  masics.append([a, b])
dp = [0] + [INF] * h

for masic in masics:
  for j in range(h):
    k = min(j+masic[0], h)
    dp[k] = min(dp[k], dp[j] + masic[1])

print(dp[h])

### FIXED CODE ###

import sys
import math
h, n = map(int, input().split())
INF = 10 ** 20
masics = []
for i in range(n):
  a, b = map(int, input().split())
  masics.append([a, b])
dp = [0] + [INF] * h

for masic in masics:
  for j in range(h):
    k = min(j+masic[0], h)
    dp[k] = min(dp[k], dp[j] + masic[1])

print(dp[h])
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)
a = int(input())
List=list(map(int,input().split()))
b = lcmm(List)
c = 0
for i in range(a):
  c = c + b // List[i] % 1000000007
print(c%1000000007)

### FIXED CODE ###

from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)
a = int(input())
List=list(map(int,input().split()))
b = lcmm(List)
c = 0
for i in range(a):
  c = c + b // List[i]
print(c%1000000007)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

from collections import defaultdict
dic = defaultdict(int)
ans = 0
for i in range(1, N+1):
    for j in range(i, N+1, i):
        dic[j]+=1
    ans += i*dic[i]
print(ans)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

dic = [0]*(N+1)
ans = 0
for i in range(1, N+1):
    for j in range(i, N+1, i):
        dic[j]+=1
    ans += i*dic[i]
print(ans)
### BUGGY CODE ###

def main():
	import sys
	readline = sys.stdin.readline

	#s = tuple(input())
	s = input().rstrip()
	n = len(s)

	dp = [[0]*13 for _ in range(n)]
	MOD = 10**9+7

	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

	a = 1
	for i in range(1,n):
		a = 10 * a % 13
		if s[-(i+1)] != '?':
			num = int(s[-(i+1)])
			for j in range(13):
				dp[i][(a*num+j)%13] += dp[i-1][j] % MOD
		else:
			num = (10**i) % 13
			#a = 0
			for j in range(10):
				for k in range(13):
					dp[i][(a*j+k)%13] += dp[i-1][k] % MOD
				#a += num

	print(dp[-1][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

def maxHeapify(heap, i):
    while (i + 1) * 2 <= len(heap):
        left = (i + 1) * 2 - 1
        right = (i + 1) * 2
        largest = left if heap[left] > heap[i] and left <= len(heap) else i
        largest = right if heap[right] > heap[largest] and right <= len(heap) else largest
        if largest != i:
            heap[i], heap[largest] = heap[largest], heap[i]
            maxHeapify(heap, largest)

def buildMaxHeap(heap):
    for i in range(len(heap) // 2, -1, -1):
        maxHeapify(heap, i)

n = int(input())
heap = list(map(int, input().split()))
buildMaxHeap(heap)
out = ''
for key in heap:
    out += ' str(key)'
print(out)

### FIXED CODE ###

def maxHeapify(heap, i):
    left = (i + 1) * 2 - 1
    right = (i + 1) * 2
    largest = left if left < len(heap) and heap[left] > heap[i] else i
    largest = right if right < len(heap) and heap[right] > heap[largest] else largest
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        maxHeapify(heap, largest)

def buildMaxHeap(heap):
    for i in range(len(heap) // 2, -1, -1):
        maxHeapify(heap, i)

n = int(input())
heap = list(map(int, input().split()))
buildMaxHeap(heap)

out = ''
for key in heap:
    out += (' {}'.format(str(key)))
print(out)
### BUGGY CODE ###

N = int(input())
S = input()
A = []
for i in range(N + 1):
	A.append(S[: i].count("#") + S[i:].count("."))
print(min(A))


### FIXED CODE ###

N = int(input())
S = input()
A = [S.count(".")]
for i in range(N):
	if S[i] == "#":
		A.append(A[i] + 1)
	else:
		A.append(A[i] - 1)
print(min(A))
### BUGGY CODE ###

from collections import defaultdict

s=input()
K=int(input())

d=defaultdict(list)
for i, si in enumerate(s):
    d[si].append(i)

sub=set()
for i in range(26):
    for j in d[chr(ord('a')+i)]:
        for k in range(len(s[j:])):
            sub.add(s[j:j+k+1])
#            print(s[j:j+k+1])
#    print(len(sub), k)    
    if len(sub)>=K:
        sub=sorted(list(sub))
        print(sub[K-1])
        break


### FIXED CODE ###

from collections import defaultdict

s=input()
K=int(input())

d=defaultdict(list)
for i, si in enumerate(s):
    d[si].append(i)

sub=set()
for i in range(26):
    for j in d[chr(ord('a')+i)]:
        for k in range(min(K,len(s[j:]))):
            sub.add(s[j:j+k+1])
#            print(s[j:j+k+1])
#    print(len(sub), k)    
    if len(sub)>=K:
        sub=sorted(list(sub))
        print(sub[K-1])
        break
### BUGGY CODE ###

#!/usr/bin/env python3

import numpy as np

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = np.array([1, 10, 9, 12, 3, 4], dtype=np.int)

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = np.zeros(13, dtype=np.int)
    priv[0] = 1
    s = S[::-1]
    for i in range(0, len(s)):
        cur = np.zeros(13+13, dtype=np.int)
        d = s[i]
        if d == '?':
            for di in range(10):
                m = (di * MODS[i % 6]) % 13
                cur[m:m+13] = (cur[m:m+13] + priv[0:13]) % P_MOD
            cur[0:13] += cur[13:26]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        priv = cur
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)


### FIXED CODE ###


P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = [1, 10, 9, 12, 3, 4]

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = [1] + [0] * 12
    # print(priv)
    s = S[::-1]
    for i in range(0, len(s)):
        cur = [0] * 13
        d = s[i]
        # print('i=', i, 'd=', d)
        if d == '?':
            for j in range(13):
                for di in range(10):
                    m = di * MODS[i % 6]
                    cur[(j+m) % 13] += priv[j]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        # print(cur)
        for j in range(13):
            priv[j] = cur[j] % P_MOD
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)
### BUGGY CODE ###

n,k_num = map(int,input().split())
info =[list(map(int,input().split())) for i in range(n)]
li_x = []
li_y = []

for i in range(n):
  if info[i][0] not in li_x:
    li_x.append(info[i][0])
  if info[i][1] not in li_y:
    li_y.append(info[i][1])

li_x = sorted(li_x)
li_y = sorted(li_y)

ans = float("inf")

for i in range(len(li_x)):
  for j in range(i,len(li_x)):
    for k in range(len(li_y)):
      for l in range(k,len(li_y)):
        count = 0
        for m in range(n):
          if li_x[i]<=info[m][0]<=li_x[j] and li_y[k]<=info[m][1]<=li_y[l]:
            count += 1
        if count ==k_num:
          ans = min(ans,(li_x[j]-li_x[i])*(li_y[l]-li_y[k]))
print(ans)

### FIXED CODE ###

n,k_num = map(int,input().split())
info =[list(map(int,input().split())) for i in range(n)]
li_x = []
li_y = []

for i in range(n):
 # if info[i][0] not in li_x:
    li_x.append(info[i][0])
 # if info[i][1] not in li_y:
    li_y.append(info[i][1])

li_x = sorted(li_x)
li_y = sorted(li_y)

bunpu = [[0]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    if info[i][0]==li_x[j]:
      zahyo_x=j
      break
  for k in range(n):
    if info[i][1]==li_y[k]:
      zahyo_y=k
      break
  bunpu[zahyo_x][zahyo_y]=1

ruiseki = [[0]*n for i in range(n)]


for i in range(0,n):
  for j in range(0,n):
    ruiseki[i][j] = bunpu[i][j]
#横方向(j)の累積
for i in range(n):
  for j in range(1,n):
    ruiseki[i][j] = ruiseki[i][j-1] + ruiseki[i][j]
#縦方向(i)の累積
for j in range(n):
  for i in range(1,n):
    ruiseki[i][j] = ruiseki[i-1][j] + ruiseki[i][j]

#print(bunpu)
#print(ruiseki)

ans = float("inf")

for i in range(len(li_x)):
  for j in range(i,len(li_x)):
    for k in range(len(li_y)):
      for l in range(k,len(li_y)):
        count = ruiseki[j][l]
        if 0<=k-1:
          count -= ruiseki[j][k-1]
        if 0<=i-1:
          count -= ruiseki[i-1][l]
        if 0<=k-1 and 0<=i-1:
          count += ruiseki[i-1][k-1]      
        if count ==k_num:
          ans = min(ans,(li_x[j]-li_x[i])*(li_y[l]-li_y[k]))
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,k=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
p=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
max = 0
#最大のリストを選定
for i in range(0,n-k+1):
    ck = sum(p[i:i+k])
    if ck > max:
        max = ck

#計算
print((max+k)/2.0)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,k=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
p=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
#最大のリストを選定
before_pi = p[0]
before_sum = sum(p[0:k])+ 0.0
suml = [sum(p[0:k])]
for i in range(1,n-k+1):
    before_sum = before_sum - before_pi+p[i+k-1]
    suml.append(before_sum)
    before_pi = p[i]

#計算
print((max(suml)+k)/2.0)
### BUGGY CODE ###

#coding:utf-8

n = int(input())
nums = list(map(int,input().split(' ')))

cnt = 0
while True:
  for num in nums:
    if num % 2 == 0:
      continue
    else:
      break
    break
  else:
    cnt += 1

### FIXED CODE ###

#coding:utf-8

n = int(input())
nums = list(map(int,input().split(' ')))

def calc():
  cnt = 0
  while True:
    for i in range(len(nums)):
      num = nums[i]
      if num % 2 == 0 and num != 0:
        nums[i] = num / 2
      else:
        return cnt
    else:
      cnt += 1

print(calc())
### BUGGY CODE ###

from collections import defaultdict
import itertools
d = defaultdict(int)
x='MARCH'
for i in range(5):
  d[x[i]]=i+1
x=[0]*5
def sub(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
N=H*W
P=[0]*(N)
for h in range(H):
  for w in range(W):
    P[A[h][w]-1]=(h,w)

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  if l>r:
    r+=N
  l,r=l-1,r-1
  ans=0
  for i in range(l+D,r+1,D):
    ans+=sub(P[i%N],P[(i-D)%N])
  print(ans)

### FIXED CODE ###

from collections import defaultdict
import itertools
d = defaultdict(int)
x='MARCH'
for i in range(5):
  d[x[i]]=i+1
x=[0]*5
def sub(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
N=H*W
P=[0]*(N)
for h in range(H):
  for w in range(W):
    P[A[h][w]-1]=(h,w)
X=[]
for d in range(D):
  _=[0]+[sub(P[i%N],P[i-D]) for i in range(d+D,N+D,D)]
  cumsum = list(itertools.accumulate(_))
  X.append(cumsum)

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  l,r=l-1,r-1
  g=l%D
  if l>r:
    r+=N
    ans=X[g][-1]-X[g][l//D]
    ans+=X[g][r//D]-X[g][0]
  else:
    ans=X[g][r//D]-X[g][l//D]
  
  print(ans)
### BUGGY CODE ###

import sys
from itertools import accumulate
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
#pypyではinitialだめ
st=[[t[i],min(accumulate(s[i],lambda a,b: a+(1 if b=="(" else -1),initial=0))] for i in range(n)]

now2=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v,w=list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for vsub in v:
    if now2+vsub[1]<0:
        print("No")
        sys.exit()
    now2+=vsub[0]
for wsub in w:
    if now2+wsub[1]<0:
        print("No")
        sys.exit()
    now2+=wsub[0]
print("Yes")

### FIXED CODE ###

import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        #いや、間違ってるのここなんかーーい
        if now2+w[i-lu-lv][1]<0:
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")
### BUGGY CODE ###

N = int(input())

def get_divisor(n):
    ans = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            ans += 1
            if n//i != i:
                ans += 1
        i += 1
    return ans

ans = 0
for i in range(1, N+1):
    ans += i * get_divisor(i)

print(ans)

### FIXED CODE ###

N = int(input())

cnt = [0]*(N+1)

for i in range(1, N+1):
    for j in range(i, N+1, i):
        cnt[j] += 1

ans = 0
for i in range(1, N+1):
    ans += i * cnt[i]

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

import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l * a[i] // fractions.gcd(l, a[i])
print(sum([l // a[i] for i in range(n)]) % 1000000007)

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l // fractions.gcd(l, a[i]) * a[i]
s = 0
for i in range(n): s += l // a[i]
print(s % 1000000007)
### BUGGY CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
#dp[v]: start from v maxpath
dp = np.ones((N),dtype=int) * -1

gragh = [[] for i in range(N)]
for _ in range(M):
    x,y = map(int, input().split())
    gragh[x-1].append(y-1)

#solve DAG and topological sort by recursive funciton
def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    return ret
for v in range(N):
    dp[v] = f(v)
print(np.max(dp))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
#dp[v]: start from v maxpath
dp = [-1 for _ in range(N)]

gragh = [[] for _ in range(N)]
for _ in range(M):
    x,y = map(int, input().split())
    gragh[x-1].append(y-1)

#solve DAG and topological sort by memo recursive funciton
def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    dp[v] = ret
    return ret
for v in range(N):
    dp[v] = f(v)
print(max(dp))
### BUGGY CODE ###

n=int(input())
a=tuple(list(map(int,input().split())))
s=0
for i in range(n-1):
    for j in range(i+1,n):
        s += a[i]^a[j]
print(s%(10**9+7))

### FIXED CODE ###

import numpy as np

n = int(input())
A = np.array([int(i) for i in input().split()])
ans = 0
#print(A & 1)

# A_iは60ビットまで与えられる.
for i in range(60):
    #A&1は配列Aを1ビット目を表示する: [1,2,3]→[1,0,1]
    c = np.count_nonzero(A & 1) #配列Aの1ビット目が非ゼロのものをカウント
    #cは桁数nを超えないのでn-c>=0
    # c*(n-c)は(0の個数)*(1の個数)を表す.
    ans += 2**i*c*(n-c) #bit毎に計算したのち2**iをかけて10進数に戻す.
    # Aを1ビット右シフト
    A >>= 1 #一つ上の桁数でも同様. 大きな位では0なので値として出てこない.
print(ans%(10**9+7))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
l=0; r=0; res=0; sum_=0; ans=[]
while True:
    if l == N and r == N:
        break
    note = r
    for i in range(r,N):
        if res ^ A[i] == sum_ + A[i]:
            r += 1
            res += A[i]
            sum_ += A[i]
        else:
            break
    length = r - l
    f = note == r
    if f is False:
        for i in range(l,r+1):
            for j in range(i+1,r+1):
                ans.append((i,j))
    if length == 0:
        r += 1
    else:
        res -= A[l]
        sum_ -= A[l]
    l += 1
ans = len(list(set((ans))))
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
r = 0; sum_ = 0; res = 0; ans = 0
for l in range(N+1):
    for i in range(r,N):
        if res ^ A[i] == sum_ + A[i]:
            r += 1
            res += A[i]
            sum_ += A[i]
        else:
            break
    length = r - l
    ans += length
    if length == 0:
        r += 1
    else:
        res -= A[l]
        sum_ -= A[l]

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

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,1))

  while len(q)>0:
    y,x,cnt=q.pop()
    if counter[y][x]<cnt:
      continue
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt+1:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,1))

  while len(q)>0:
    y,x,cnt=q.pop()
    if counter[y][x]<cnt:
      continue
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt+1:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return h*w-sharp_cnt-step_cnt

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

# coding: utf-8
N=int(input())
L=list(map(int,input().split()))
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            l=[L[i],L[j],L[k]]
            #print(l)
            m=max(l)
            l.remove(m)
            if m<sum(l):
                ans+=1
print(ans)

### FIXED CODE ###

from bisect import bisect_right
 
N = int(input())
L = sorted(list(map(int, input().split())))
 
ans = 0
for i in range(1, N-1):
    for j in range(i+1, N):
        ans += max(0, i - bisect_right(L, L[j] - L[i]))
print(ans)
### BUGGY CODE ###

N = int(input())
even = True if N % 2 == 0 else False

start = 0
end = N-1

print(0)
s0 = input()
if s0 == 'Vacant':
    exit()

ni = (start+end)//2
print(ni)
s = input()

while s != 'Vacant':
    if (s == s0) ^ (s % 2 == s0 % 2):
        start = ni+1
    else:
        end = ni

    s0 = s

    ni = (start+end)//2
    print(ni)
    s = input()

exit()


### FIXED CODE ###

N = int(input())


def ask(i):
    print(i, flush=True)
    resp = input()
    if resp == 'Vacant':
        exit()
    return resp


def test(l, r, l_resp, r_resp):
    if l % 2 == r % 2:
        return l_resp == r_resp
    else:
        return l_resp != r_resp


resp = ask(0)

l = 0
r = N
l_resp = resp
r_resp = resp

for _ in range(19):
    m = (l+r)//2
    m_resp = ask(m)
    if test(l, m, l_resp, m_resp):
        l, l_resp = m, m_resp
    else:
        r, r_resp = m, m_resp
### BUGGY CODE ###

S=input()
Q=int(input())

f=1
for _ in range(Q):
    A=[]
    A.clear()
    A=list(input().split())
    if A[0]=="1":
        f*=-1
    if A[0]=="2":
        if A[1]=="1":
            if f==1:
                S=A[2]+S
            if f==-1:
                S=S+A[2]
        if A[1]=="2":
            if f==-1:
                S=A[2]+S
            if f==1:
                S=S+A[2]

if f==-1:
    S="".join(list(reversed(S)))

print(S)


### FIXED CODE ###

S=input()
Q=int(input())

X=[]
Y=[]
f=1
for _ in range(Q):
    A=list(input().split())
    if A[0]=="1":
        f*=-1
    if A[0]=="2":
        if A[1]=="1":
            if f==1:
                X.append(A[2])
            if f==-1:
                Y.append(A[2])
        if A[1]=="2":
            if f==-1:
                X.append(A[2])
            if f==1:
                Y.append(A[2])

x="".join(X)
x="".join(list(reversed(x)))
y="".join(Y)

a=[x,S,y]
b="".join(a)

if f==-1:
    b="".join(list(reversed(b)))

print(b)
### BUGGY CODE ###

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
	for j in range(W + 1):
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])
# print(dp)


### FIXED CODE ###

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
	for j in range(W + 1):
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])
### BUGGY CODE ###

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

ans = 0

for b in B:
    ans += len(list(filter(lambda x: x < b, A))) * \
        len(list(filter(lambda x: x > b, C)))

print(ans)


### FIXED CODE ###

from itertools import accumulate

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

acc_a = [0]*N
acc_c = [0]*N

i_a = 0
i_c = N-1
for i in range(N):
    b = B[i]
    while i_a < N and A[i_a] < b:
        acc_a[i] += 1
        i_a += 1

for i in reversed(range(N)):
    b = B[i]
    while i_c >= 0 and C[i_c] > b:
        acc_c[i] += 1
        i_c -= 1

acc_a = list(accumulate(acc_a))
acc_c = list(accumulate(acc_c[::-1]))
acc_c = acc_c[::-1]

ans = 0
for a, c in zip(acc_a, acc_c):
    ans += a*c
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[0]*N
for i in range(1,N):
  ans[i]=A.count(i)
  print(ans[i])
print(A.count(N))


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[0]*N
for i in range(N-1):
  ans[A[i]]+=1
del ans[0]
ans.append(A.count(N))
for i in range(N):
  print(ans[i])
### BUGGY CODE ###

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

nin=min(a)
nax=max(a)
ans=0
for x in range(nin,nax+1):
    temp=[]
    for i in range(N):
        tt=abs(a[i]-x)
        if -1<=tt and tt<=1:
            temp.append(1)
    ans=max(ans,sum(temp))

print(ans)


### FIXED CODE ###

import collections
N=int(input())
a=list(map(int,input().split()))

for i in range(N):
    a.append(a[i]-1)
    a.append(a[i]+1)

cc=collections.Counter(a)
ans=max(list(cc.values()))

print(ans)