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

import sys
#input = sys.stdin.buffer.readline
import numpy as np
 
def main():
    H,W,K = map(int,input().split())
    a = [input() for _ in range(H)]
    
    x = np.zeros((H,W+1),dtype=int)
    for i in range(H):
        for j in range(W):
            if a[i][j] == "1":
                x[i][j+1] = 1
            else:
                x[i][j+1] = 0

    ans = 10**5
    for i in range(1<<H-1):
        use = np.zeros((H,W+1),dtype=int)
        u,now,count = 0,0,0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                count += 1
                bl = x[u:j+1,:]
                bl = np.sum(bl,axis=0)
                u = j+1
                use[now] = bl
                now += 1
        bl = np.sum(x[u:,:],axis=0)
        use[now] = bl
        use = np.cumsum(use,axis=1)
        l,r = 0,1
        while r<=W:
            f = use[:,r]-use[:,l]
            if np.max(f) > K:
                count += 1
                l = r-1
            r += 1
        ans = min(ans,count)
        
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = S = [list(map(int, list(input()))) for _ in range(H)]
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        bl,yorn = [0 for _ in range(l)],True
        for right in range(W):
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import defaultdict

def main():
    N, M = map(int, input().split())
    a = [input().split() for _ in range(M)]
    fin = []
    wa_count = defaultdict(lambda:0)
    ac, wa = 0, 0

    for q_no, ans in a:
        if ans == "AC":
            if q_no in fin:
                continue
            else:
                fin.append(q_no)
                ac += 1
                wa += wa_count.get(q_no, 0)
        else:
            wa_count[q_no] += 1
    
    print(ac, wa)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict

def main():
    N, M = map(int, input().split())
    a = [input().split() for _ in range(M)]
    ac_count = [0] * (N + 1)
    wa_count = defaultdict(lambda:0)
    ac, wa = 0, 0

    for q_no, ans in a:
        q_no = int(q_no)
        if ac_count[q_no] == 0:
            if ans == "AC":
                ac_count[q_no] = 1
                ac += 1
                wa += wa_count.get(q_no, 0)
            else:
                wa_count[q_no] += 1
    
    print(ac, wa)

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

import sys, os, math

def get_cd(n):
    cd = []
    for i in range(1, int(n/2)+1):
        if n % i == 0:
            cd.append(i)
        else:
            continue
    cd.append(n)
    return cd

def get_gcd(a, b, c, cd_d):
    if 1 in [a, b, c]:
        return 1
    else:
        min_v = min([a,b,c])
        cds_min = cd_d[min_v]
        gcd = 1
        for cd in reversed(cds_min):
            if cd in cd_d[a]:
                if cd in cd_d[b]:
                    if cd in cd_d[c]:
                        return cd
                    else: continue
                else: continue
            else:continue

if __name__ == '__main__':
    k = int(input())
    cc_d = {}
    for i in range(1, k+1):
        cc_d[i] = get_cd(i)

    computed_d = {}
    s = 0
    for a in range(1, k+1):
        for b in range(a, k+1):
            for c in range(b, k+1):
                sort_str = "".join([ str(i) for i in sorted([a,b,c])])
                gcd = get_gcd(a, b, c, cc_d)
                if a == b == c:
                    s += gcd
                elif a == b or a == c or b == c:
                    s += gcd*3
                else:
                    s += gcd*6
    print(s)

### FIXED CODE ###

import sys, os, math

def get_cd(n):
    cd = []
    for i in range(1, int(n/2)+1):
        if n % i == 0:
            cd.append(i)
        else:
            continue
    cd.append(n)
    return cd

def get_gcd(a, b, c, cd_d):
    if 1 in [a, b, c]:
        return 1
    else:
        cd = sorted(list(set(cd_d[a]) & set(cd_d[b]) & set(cd_d[c])))
        return cd[-1]

if __name__ == '__main__':
    k = int(input())
    cc_d = {}
    for i in range(1, k+1):
        cc_d[i] = get_cd(i)

    computed_d = {}
    s = 0
    for a in range(1, k+1):
        for b in range(a, k+1):
            for c in range(b, k+1):
                if a == b == c:
                    s += a
                else:
                    gcd = get_gcd(a, b, c, cc_d)
                    if a != b != c:
                        s += gcd*6
                    else:
                        s += gcd*3
    print(s)
### BUGGY CODE ###

n, k = [int(x) for x in input().split()]
hs = [0] + [int(x) for x in input().split()]
dp = [0] * (n+1)
mx = 1 << 50
for i in range(2, n + 1):
    mn = mx
    minIndex = max(1, i - k)
    for j in range(minIndex, i):
        v = dp[j] + abs(hs[i] - hs[j])
        if v < mn:
            mn = v
    dp[i] = mn
print(dp[n])

### FIXED CODE ###

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

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

dp = [0] * n

for i in range(1, min(k,n)):
	dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[:i], hs[:i])])

if k < n:
	for i in range(k, n):
		dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[i-k:i], hs[i-k:i])])

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

N,X,Y = map(int,input().split())
data = [[3000]*N for _ in range(N)]
for i in range(N-1):
  data[i][i+1] = 1
  data[i+1][i] = 1
  data[i][i] = 0
data[0][0] = 0
data[X-1][Y-1] = 1
data[Y-1][X-1] = 1
for k in range(N):
  for i in range(N):
    for j in range(N):
      data[i][j] = min(data[i][j],data[i][k]+data[k][j])
for i in range(N-1):
  counter = 0
  for j in range(N):
    counter += data[j].count(i+1)
  print(int(counter//2))

### FIXED CODE ###

N,X,Y = map(int,input().split())
a = [0]*(N-1)
for i in range(1,N):
  for j in range(i+1,N+1):
    ans = min(j-i,abs(X-i)+1+abs(Y-j),abs(X-j)+1+abs(Y-i))
    a[ans -1] += 1
for item in a:
  print(item)
### BUGGY CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))

if 0 in a:
    print(0)
    sys.exit()
    
ans = 1
for i in a:
    ans *= i
    
if ans <= 1000000000000000000:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))

if 0 in a:
    print(0)
    sys.exit()
    
ans = 1
for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        sys.exit()
print(ans)
### BUGGY CODE ###

n = int(input())
rslt = 1
while n > 0:
    rslt *= n
    n -= 1
print(rslt%(10**9+7))

### FIXED CODE ###

import math
n = int(input())
print( math.factorial(n)%(10**9+7) )
### BUGGY CODE ###

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

ans = set()
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            ans.add(S[i] + S[j] + S[k])

print(len(ans))


### FIXED CODE ###

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

ans = set()
for i in range(10):
    i_index = S.find(str(i))
    if i_index == -1:
        continue
    for j in range(10):
        j_index = S.find(str(j), i_index+1)
        if j_index == -1:
            continue
        for k in range(10):
            k_index = S.find(str(k), j_index+1)
            if k_index == -1:
                continue
            ans.add("{}{}{}".format(i, j, k))

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

S = input()
mod = 2019
DP = [0] * mod
DP[0] = 1
t = 1
value = 0
for i in reversed(S):
    value += int(i) * t
    res = value % mod
    DP[res] += 1
    t *= 10
print(int(sum([i * (i-1) / 2 for i in DP])))

### FIXED CODE ###

S = input()
N = len(S)
mod = 2019
num = [0 for i in range(2019)]
num[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    num[rem] += 1

print(int(sum([i * (i-1) / 2 for i in num])))
### BUGGY CODE ###

from math import gcd
a,b,n=map(int,input().split())
t=a*b//gcd(a,b)
if a==1:
    print(0)
    exit()

ans=0
if n%t!=0:
    n%=t

for i in range(1,n+1):
    y=int(a*i/b)-a*int(i/b)
    ans=max(ans,y)


print(ans)


### FIXED CODE ###


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

def f(x):
    return a*x//b-a*(x//b)

print(f(min(n,b-1)))
### BUGGY CODE ###

def lma():return list(map(int, input().split()))#x or y

a = int(input())
k=[]
s=[]
co=[0]*a*3
c=0
s= [lma()]
x2= lma()
x3 = lma()
s.append(x2)
s.append(x3)
res =0
for j in range(3):
    for i in range(a):
        k.append([j,s[j][i]])
k.sort(key=lambda x: x[1], reverse=True)
for i in range(a*3):
    if k[i][0] == 2:
       c+=1
    elif k[i][0] == 1:
       co[i] = c
    else:
       res+=sum(co[:i])
print(res)
       

### FIXED CODE ###

def lma():return list(map(int, input().split()))#x or y
a = int(input())
k=[]
s=[]
c=0
s= [lma()]
x2= lma()
x3 = lma()
s.append(x2)
s.append(x3)
res =0
r =0
for j in range(3):
    for i in range(a):
        k.append([j,s[j][i]])
k.sort(key=lambda x: x[1], reverse=True)
for i in range(a*3):
    if k[i][0] == 2:
       c+=1
    elif k[i][0] == 1:
       r+=c 
    else:
       #res+=sum(co[:i])
        res+=r
print(res)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
ikeruheya = [[] for i in range(n)]
ans = [0]*(n+1)
check = [0]*n

for i in range(m):
    ikeruheya[a[i][0]-1].append(a[i][1])
    ikeruheya[a[i][1]-1].append(a[i][0])
    
next=[1]
count = 1
while len(next) != 0 and count < n + 1:
    imaheya = next.pop(0)
    for j in range(len(ikeruheya[imaheya-1])):
        if check[ikeruheya[imaheya-1][j]-1]==0:
            ans[ikeruheya[imaheya-1][j]]= imaheya 
            check[ikeruheya[imaheya-1][j]-1] = 1
            next.append(ikeruheya[imaheya-1][j])
            count += 1
            
print("Yes")
for i in range(2, n+1):
    print(ans[i])

    
    
    


### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(m)]
b=[[] for j in range(n)] 

michi=[-1]*(n)
michi[0]=0
heya=[]


for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])



heya.append(1)


while len(heya):
    now=heya.pop(0)-1
    
    for i in range(len(b[now])):
        if michi[b[now][i]-1] == -1:
            heya.append(b[now][i])
            michi[b[now][i]-1] = now+1
print("Yes")
for i in range(1,n):
    print(michi[i])
### BUGGY CODE ###

N, b, r = list(map(int, input().split()))
str = ''
loop, cnt = 0, 0
while(cnt <= N):
  if loop%2 == 0:
    for i in range(b):
    	str += 'b'
    cnt += b
  elif loop%2 == 1:
    for i in range(r):
    	str += 'r'
    cnt += r
  loop += 1
cnt = 0
for i in range(N):
  if str[i] == 'b':
    cnt += 1
print(cnt)

### FIXED CODE ###

N, b, r = list(map(int, input().split()))
if b==0 and r==0:
  print(0)
  exit()
  
c = N//(b+r)
if N%(b+r) == 0:
  print(b*c)
else:
  if N%(b+r) <= b:
    print(c*b + N%(b+r))
  else:
    print(b*c + b)
### BUGGY CODE ###

n=int(input())
ans=0
while n:
  a,b=1,1
  while a*6>n:
    a*=6
  while b*9>n:
    b*=9
  n-=max(a,b)
  ans+=1
print(ans)
  
  

### FIXED CODE ###

n=int(input())
ans=1000000000
for i in range(0,n+1,6):
  j=n-i
  a=0
  while j:
    a+=j%9
    j//=9
  while i:
    a+=i%6
    i//=6
  ans=min(a,ans)
print(ans)
### BUGGY CODE ###

# input
N, M, K = map(int, input().split())

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a < b:
        Frends[a].append(b)
    else:
        Frends[b].append(a)

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if c < d:
        Blocked[c].append(d)
    else:
        Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        t = -1

        j = 0
        maxj = len(fg)
        while j < maxj:
            g = fg[j]
            if i in g and f in g:
                if t < 0:
                    t = j              
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    maxj -= 1
            elif not (i in g or f in g):
                j += 1
                continue
            else:
                if t < 0:
                    if i in g:
                        g.add(f)
                    else:
                        g.add(i)

                    t = j
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    maxj -= 1
            j += 1

        if t < 0:
            fg.append(set([i, f]))

# 友人候補を抽出
cand = []
for i in range(N):
    for g in fg:
        if i in g:
            for f in g:
                if i < f and not f in Frends[i] and not f in Blocked[i]:
                    cand.append((i, f,))

# 友人候補をカウント
ans = [0 for _ in range(N)]
for c in cand:
    a, b = c
    ans[a] += 1
    ans[b] += 1

# output
#print(fg)
#print(cand)
print(" ".join(map(str, ans)))


### FIXED CODE ###

# input
N, M, K = map(int, input().split())

Friends = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Friends[a].add(b)
    Friends[b].add(a)

Blocked = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].add(d)
    Blocked[d].add(c)

# process
# 友人グループを作成
checked = set()
ans = [0]*N

for i in range (N):
    if i in checked:
        continue
    
    fg = set()

    stack = list(Friends[i])
    while stack:
        f = stack.pop()
        if f in checked:
            continue

        checked.add(f)
        fg.add(f)
        stack.extend(Friends[f])

    for f in fg:
        ans[f] += len(fg)-1-len(fg&(Friends[f]|Blocked[f]))

# output
print(" ".join(map(str, ans)))
### BUGGY CODE ###

R, G, B, N = (int(i) for i in input().split())

RGB = [R, G, B]
RGB.sort(reverse=False)

c = 0
for r in range(N//RGB[0], -1, -1): 
    new1 = N - r*RGB[0]
    for g in range(new1//RGB[1], -1, -1):
        new2 = new1 - g*RGB[1]
        c += len([b for b in range(new2//RGB[2], -1, -1) if b*RGB[2] == new2])

print(c)

### FIXED CODE ###

R, G, B, N = (int(i) for i in input().split())

c = 0
for r in range(N//R, -1, -1): 
    new1 = N - r*R
    for g in range(new1//G, -1, -1):
        new2 = new1 - g*G
        if new2%B == 0:
            c +=1
    
print(c)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
ans = m//n
while m%ans!=0:
  ans -= 1
print(ans)

### FIXED CODE ###

n, m = list(map(int, input().split()))
ans = m//n
while m%ans!=0:
  ans -= 1
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
n = input()
tmp = input().split(" ")
l = (int(e) for e in tmp)
res = 1
res = reduce(mul,l)
if res > 1e+18:
    print("-1")
else:
    print(res)

### FIXED CODE ###

from operator import mul
from functools import reduce
n = input()
tmp = input().split(" ")
l = sorted([int(e) for e in tmp])
def solve():
    res = 1
    for e in l:
        res = e*res
        if res > 1e+18:
            print("-1")
            return
    print(res)
solve()
### BUGGY CODE ###

s=input()
def check(s):
    x=s[-3:]
    if x=='eam':
        if s[-5:]=='dream':
            return 'dream'
    elif x=='mer':
        if s[-7:]=='dreamer':
            return 'dreamer'
    elif x=='ase':
        if s[-5:]=='erase':
            return 'erase'
    elif x=='ser':
        if s[-6:]=='eraser':
            return 'eraser'
    else: return 'False'

count=0
while len(s)>0 and count==0:
    if check(s)=='False':
        count+=1
        print('NO')
    elif check(s)=='dream' or check(s)=='erase':
        if len(s)!=5:s=s[:-5]
        elif len(s)==5:s=''
    elif check(s)=='eraser':
        if len(s)!=6:s=s[:-6]
        elif len(s)==6:s=''
    elif check(s)=='dreamer':
        if len(s)!=7:s=s[:-7]
        elif len(s)==7:s=''

if count==0:print('YES')

### FIXED CODE ###

s=input()
def check(s):
    if s[-5:]=='dream':
        return 'dream'
    elif s[-7:]=='dreamer':
        return 'dreamer'
    elif s[-5:]=='erase':
        return 'erase'
    elif s[-6:]=='eraser':
        return 'eraser'
    else: return 'False'

count=0
while len(s)>0 and count==0:
    if check(s)=='False':
        count+=1
        print('NO')
    elif check(s)=='dream' or check(s)=='erase':
        s=s[:-5]
    elif check(s)=='eraser':
        s=s[:-6]
    elif check(s)=='dreamer':
        s=s[:-7]

if count==0:print('YES')
### 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

t2_max = accT[-1] * 2
speeds = [INF] * (t2_max + 1)
for t0, t1, v in zip(accT[:-1], accT[1:], V):
    for t2 in range(0, t0 * 2):
        speeds[t2] = min(speeds[t2], (t0 - t2 * 0.5) + v)
    for t2 in range(t0 * 2, t1 * 2):
        speeds[t2] = min(speeds[t2], v)
    for t2 in range(t1 * 2, t2_max + 1):
        speeds[t2] = min(speeds[t2], (t2 * 0.5 - t1) + v)

ans = sum(speeds) / 2

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 heapq
import sys

n = int(input())
*l, = map(int, input().split())
heapq.heapify(l)
c = 0
s = []
try:
    for i in range(n):
        while len(s) < 2:
            s.append(heapq.heappop(l))
        m = heapq.heappop(l)
        for j in range(len(s)):
            for k in range(j+1, len(s)):
                if m < s[j] + s[k]:
                    c += 1
        s.append(m)
except:
    print(c)
    sys.exit(0)
print(c)

### FIXED CODE ###

import sys
import bisect

n = int(input())
*l, = map(int, input().split())
l.sort()
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        c = bisect.bisect_left(l, l[i] + l[j], j+1)
        ans += c - j - 1

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

# cook your dish here
import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
a.sort()
 
b = 1
while b <= a[n-1]:
    b = b*2

c = [None]*n #使ったら1
 
res = 0
 
for i in range(n-1,-1,-1):
    if c[i] == None:
        
        while b > a[i]:
            b = b//2
        b = b*2
        w1 = bisect.bisect_left(a,b-a[i])
        w2 = bisect.bisect_right(a,b-a[i])
        if w2 >w1:
            for p in range(w1,w2):
                if c[p] == None and i != p:
                    res += 1
                    c[p] = 1
                    c[i] = 1
                    break
                
 
print(res)

### FIXED CODE ###

import bisect
 
N = int(input())
A = [int(a) for a in input().split()]
A = sorted(A)
 
c = 0
for i in range(N - 1 , -1, -1):
    if A[i] == int(A[i]):
        b = 1
        while b <= A[i]:
            b <<= 1
 
        j = bisect.bisect_left(A, b - A[i])
        if i > j:
            if b - A[i] == A[j]:
                c += 1
                A[j] = A[j] - 0.5
                A[i] = A[i] + 0.5
print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

R, C, K = map(int, readline().split())

data = [[0]*(C+1) for _ in range(R+1)]
for i in range(K):
    r,c,v = map(int,readline().split())
    data[r][c] = v

dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

dp[1][1][1] = data[1][1]

for i in range(1,R+1):
    for j in range(1,C+1):
        for k in range(4):
            if i+1 < R+1:
                dp[i+1][j][0] = max(dp[i+1][j][0],dp[i][j][k])
                dp[i+1][j][1] = max(dp[i+1][j][1],dp[i][j][k]+data[i+1][j])     
            if j+1 < C+1:
                dp[i][j+1][k] = max(dp[i][j][k],dp[i][j+1][k])
                if k+1 <= 3:
                    dp[i][j+1][k+1] = max(dp[i][j+1][k+1],dp[i][j][k]+data[i][j+1])
            
print(max(dp[i][j]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

R, C, K = map(int, readline().split())

V = [[0]*(C+1) for _ in range(R+1)]
for i in range(K):
    r,c,v = map(int,readline().split())
    V[r][c] = v

dp = [0] * (C+1)
dp[0] = 0

for i in range(1,R+1):
    ndp = [0] * (C+1)
    row = V[i]
    ldp = [0] * 4
    for j in range(1,C+1):
        # ldp[0] = max(ldp[0], dp[j])
        ldp[0] = dp[j]
        for k in range(2,-1,-1):
            ldp[k+1] = max(ldp[k+1], ldp[k] + row[j]) # 取る場合と取らない場合
        ndp[j] = max(ldp)
    dp = ndp
print(dp[C])
### BUGGY CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=Counter(a)
t=[]
for _ in b.most_common(100):
  t.append(len([i for i in a if _[0]-1<i<_[0]+3]))
  t.append(len([i for i in a if _[0]-2<i<_[0]+2]))
  t.append(len([i for i in a if _[0]-3<i<_[0]+1]))
print(max(t))

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=[i-1 for i in a]+a+[i+1 for i in a]
b=Counter(b).most_common(1)
print(b[0][1])
### BUGGY CODE ###

N,K=(input().split())
N,K=int(N),int(K)
seq=list(input().split())
seq=[int(x) for x in seq]
cou=0
C=0
inc=0
for i in range(len(seq)):
    for j in range(i+1,len(seq)):
        if seq[i]>seq[j]: cou+=1
        if seq[i]<seq[j]: inc+=1
for m in range(K):
    C+=((K-m)*cou+m*inc)%1000000007
    C=C%1000000007
C=C%1000000007
print(C)

### FIXED CODE ###

N,K=(input().split())
N,K=int(N),int(K)
seq=list(input().split())
seq=[int(x) for x in seq]
cou=0
C=0
inc=0
for i in range(len(seq)):
    for j in range(i+1,len(seq)):
        if seq[i]>seq[j]: cou+=1
for i in range(len(seq)):
    for j in range(len(seq)):
        if seq[i]>seq[j]: inc+=1
C=(K*(K-1)//2)*inc+K*cou
print(C%(10**9+7))
### BUGGY CODE ###

import numpy as np
from numpy.fft import fft
from numpy.fft import ifft
class FFT:
  def exe(s, A, B):
    N = len(A) + len(B) - 1
    A, B = s.arrN(N, A), s.arrN(N, B)
    A = fft(A) * fft(B)
    A = ifft(A).real + 0.5
    return list(map(int, A))
  def arrN(s, N, L):
    return np.zeros(N) + (L + [0] * (N - len(L)))

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

MAX = max(A)
L = [0] * (MAX + 1)
for i in A:
  L[i] += 1

f = FFT()
L = f.exe(L, L)

ans = 0
for i in range(len(L) - 1, -1, -1):
  if L[i] < M:
    ans += i * L[i]
    M -= L[i]
  else:
    ans += i * M
    break

print(ans)


### FIXED CODE ###

def nibutan(n, M):
  ok = 0
  ng = M + 1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    #print("value:", mid)
    if nasu(mid) >= n:
      ok = mid
    else:
      ng = mid
  return ok

def nasu(x):
  ans = 0
  for i in A:
    #print("L:", i, end = " ")
    t = N - hogetan(x - i)
    #print("n:", t)
    ans += t
  return ans

def hogetan(n):
  ok = N
  ng = -1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if A[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

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


A.sort()
MAX = A[-1] + A[-1]
inf = MAX + 10

t = nibutan(M, MAX)
mi = inf
cnt = 0
ans = 0
for i in A:
  k = hogetan(t - i)
  n = N - k
  cnt += n
  if n != 0:
    mi = min(mi, i + A[k])
  ans += n * 2 * i

ans -= mi * (cnt - M)

print(ans)