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

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

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in sys.stdin.readline().split(' ')])


dp = np.zeros((N + 1, W + 1), dtype = 'uint64')
for i in range(N):
    for w in range(W + 1):
        if w - WV[i][0] >= 0:
            dp[i + 1][w] = max(dp[i + 1][w], WV[i][1] + dp[i][w - WV[i][0]])
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
print(dp[N][W])



### FIXED CODE ###

import numpy as np
import sys

N, W = [int(v) for v in input().strip().split(' ')]
dp = np.zeros(W + 1, dtype = 'uint64')

for _ in range(N):
    w, v = [int(v) for v in sys.stdin.readline().split(' ')]
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])

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

def abc094C():
    n = int(input())
    x = input().split()
    x = list(map(int, x))
    for i in range(n):
        y = x.copy()
        del y[i]
        y.sort()
        print(y[int(n / 2)-1])


abc094C()

### FIXED CODE ###

def abc094C():
    n = int(input())
    x = input().split()
    x = list(map(int, x))
    y = x.copy()
    y.sort()
    nums = y[int(n / 2 - 1): int(n / 2 + 1)]
    for i in range(n):
        tf = nums[0] >= x[i]
        print(nums[tf])


abc094C()
### BUGGY CODE ###

import sys
input = sys.stdin.readline


N = int(input())
A = ["?"]*N


def f2(i):
    global A
    s = A[i]
    if s == "?":
        print(i, flush=True)
        s = input().strip()
        A[i] = s
    if s == "Vacant":
        exit()
    return s


def f(l, r):
    m = (l+r)//2
    f2(m)

    if ((m-l) % 2 and A[l] == A[m]) or ((m-l) % 2 == 0 and A[l] != A[m]):
        f(l, m-1)
    elif ((r-m) % 2 and A[m] == A[r]) or ((r-m) % 2 == 0 and A[m] != A[r]):
        f(m+1, r)


def main():
    f2(0)
    f2(N-1)
    f(0, N-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def q(i):
    print(i, flush=True)
    s = input().strip()
    if s == "Vacant":
        exit()
    return s


def f(l, r, lc, rc):
    m = (l+r)//2
    mc = q(m)

    if ((m-l) % 2 and lc == mc) or ((m-l) % 2 == 0 and lc != mc):
        f(l, m, lc, mc)
    elif ((r-m) % 2 and mc == rc) or ((r-m) % 2 == 0 and mc != rc):
        f(m, r, mc, rc)


def main():
    N = int(input())
    lc = q(0)
    rc = q(N-1)
    f(0, N-1, lc, rc)


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

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(1,k+1):
    a[i] = a[i] * a[i-1]

if a[k]/a[0] <= a[k-1]:
    print('No')
else:
    print('Yes')
for i in range(k+1,n):
    a[i] = a[i] * a[i-1]
    if a[i]/a[i-k] <= a[i-1]/a[i-k-1]:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(k,n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
def get_counter(s):
    return Counter(s.upper().replace(' ', ''))

n=int(input())
a=[get_counter(input().rstrip('\r\n')) for i in range(n)]

def r(n):
    cnt=0
    for i in range(n):
        cnt+=i+1
    return cnt

fin=0
res=0
while len(a)>=fin:
    b=[]
    cnt=0
    i=1
    for _ in range(1,len(a)):
        if a[0]==a[i]:
            cnt+=1
            a.pop(i)
        else:
            i+=1
    a.pop(0)
    fin+=1
    res+=r(cnt)
print(res)

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
def get_counter(s):
    return Counter(s.upper().replace(' ', ''))

n=int(input())
#a=[get_counter(input().rstrip('\r\n')) for i in range(n)]
a=["".join(sorted(input().rstrip('\r\n'))) for i in range(n)]
def r(n):
    cnt=0
    for i in range(n):
        cnt+=i+1
    return cnt

my_dic={}
for i in a:
    if i in my_dic:
        my_dic[i]+=1
    else:
        my_dic[i]=1

res=0
for i in my_dic.values():
    res+=r(i-1)
        
print(res)
### BUGGY CODE ###

x = int(input())
ans = 0
for a in range(1,1000):
  for b in range(1,1000):
    if a**b <= 1000:
      ans = max(ans,a**b)
print(ans)

### FIXED CODE ###

x = int(input())
ans = 0
for a in range(2,x):
  for b in range(2,10):
    if a**b <= x:
        ans = max(ans,a**b)
        #print(a,b)
if x == 1:
    print(1)
    exit()
print(ans)
### BUGGY CODE ###

s = list(map(int, list(input())))
ls = len(s)
while True:
    f = False
    for i in range(len(s)-1):
        if (s[i] ==0 and s[i+1] ==1) or (s[i] ==1 and s[i+1] ==0):
            s[i], s[i+1] = '', ''
            f = True
    while '' in s:
        s.remove('')
    if f == False:
        break
print(ls-len(s))

### FIXED CODE ###

s = list(input())
print(min(s.count('1'), s.count('0'))*2)
### BUGGY CODE ###

import numpy as np
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.csgraph import shortest_path
M=49*50+1
n,m,s=map(int,input().split())
s=min(s,M-1)
G=lil_matrix((n*M,n*M),dtype=np.int64)
for _ in range(m):
    a,b,silver,time=map(int,input().split())
    a-=1
    b-=1
    for i in range(silver,M):
        G[a*M+i,b*M+i-silver]=time
        G[b*M+i,a*M+i-silver]=time
for i in range(n):
    silver,time=map(int,input().split())
    for j in range(M-1):
        G[i*M+j,i*M+min(j+silver,M-1)]=time
G=G.tocsr()
G=shortest_path(G,method='D',indices=s) # D=VlogE ndarray

for i in range(1,n):
    ans=np.min(G[i*M:i*M+M])
    print(int(ans))

### FIXED CODE ###

from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
lasttime=[[10**15]*2501 for i in range(n)]
lasttime[0][min(2500,s)]=0
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]#(time,silver,node)

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        nexttime,nextsilver=time+costtime,silver-costmoney
        if costmoney<=silver and lasttime[atnode][nextsilver]>nexttime:
            heappush(hp,(nexttime,nextsilver,atnode))
            lasttime[atnode][nextsilver]=min(lasttime[atnode][nextsilver],nexttime)

    nexttime,nextsilver=time+d[node],min(silver+c[node],2500)
    if silver!=2500 and lasttime[node][nextsilver]>nexttime:
        heappush(hp,(nexttime,min(silver+c[node],2500),node))
        lasttime[node][nextsilver]=min(lasttime[node][nextsilver],nexttime)
        
print(*mintimes[1:],sep="\n")
### BUGGY CODE ###

import math
n,a,b=map(int,input().split())
h=[]
for i in range(n):
    h.append(int(input()))
def sten(t):
    dh=[]
    for i in range(n):
        if h[i]-t*b>0:
            dh.append(h[i]-t*b)
    aan=0
    for i in range(len(dh)):
        aan+=math.ceil(dh[i]/(a-b))
    if aan<=t:
        return True
    else:
        return False
i=1
while True:
    if sten(i):
        print(i)
        break
    else:
        i+=1

### FIXED CODE ###

import math
n,a,b=map(int,input().split())
h=[]
for i in range(n):
    h.append(int(input()))
def sten(t):
    dh=[]
    for i in range(n):
        if h[i]-t*b>0:
            dh.append(h[i]-t*b)
    aan=0
    for i in range(len(dh)):
        aan+=math.ceil(dh[i]/(a-b))
    if aan<=t:
        return True
    else:
        return False

left = 0
right = int(1e9)
while left < right:
    center = (left + right) // 2
    if sten(center):
        right = center
    else:
        left = center + 1
print(left)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)


H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append(input())

def rec(h,w):
    seen[h][w]=1
    step=[[0,1],[0,-1],[1,0],[-1,0]]
    ret=0
    for dh,dw in step:
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if seen[nh][nw]==0 and S[nh][nw]==".":
                ret+=1
                seen[nh][nw]=1
                for ddh,ddw in step:
                    if 0<=nh + ddh<H and 0<=nw + ddw < W:
                        if seen[nh+ddh][nw+ddw]==0 and S[nh+ddh][nw+ddw]=="#":
                            ret+=rec(nh+ddh,nw+ddw)
    return ret


ans=0
for h in range(H):
    for w in range(W):
        seen=[[0]*W for _ in range(H)]
        if S[h][w]=="#":
            ans+=rec(h,w)

print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append(input())

def DFS(h,w,black,white,m):
    black,white=BorW(h,w,black,white)
    step=[[0,1],[0,-1],[1,0],[-1,0]]
    seen[h][w]=1
    for dh,dw in step:
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if seen[nh][nw]==0 and m!=S[nh][nw]:
                seen[nh][nw]=1
                black,white=DFS(nh,nw,black,white,S[nh][nw])
    return black,white


def BorW(h,w,black,white):
    if S[h][w]=="#":
        black+=1
    else:
        white+=1
    return black,white


seen=[[0]*W for _ in range(H)]

L=[]
for h in range(H):
    for w in range(W):
        black=0
        white=0
        if seen[h][w]==0:
            black,white=DFS(h,w,black,white,S[h][w])
            L.append([black,white])
ans=0
for b,w in L:
     ans+=b*w

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

import numpy as np
n, k = map(int, input().split())
P = list(map(int, input().split()))
#n = 10
#k = 4
#P = [17, 13, 13, 12, 15, 20, 10, 13, 17, 11]
ans2 = list()
for i in range(n - (k-1)):
    ans2.append(P[i:i+k])
#print(ans2)

ans3 = list()
for i in ans2:
    ans3.append(sum(i))
#print(ans3)

am = np.argmax(ans3)
#print(am)
am2 = P[am:am+k]
#print(am2)

ans = 0
for i in am2:
    for j in range(1, i + 1):
        ans += j / i
print(ans)

### FIXED CODE ###

from itertools import accumulate

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

# 期待値の前計算
expP = [(P[i]+1)/2 for i in range(n)]

# 累積和の計算
acc = [0]+ list(accumulate(expP)) # 0を忘れずに

# 隣接する K 項の和の計算
ans = 0
for i in range(n-k+1):
  ans = max(ans,acc[i+k]-acc[i])
print(ans)
### BUGGY CODE ###

n = input()
l = []
for i in range(int(n)):
	command = input()
	if command[0] == 'i':
		l.insert(0, command[7:])
	else:
		if command[6] == " ":
			if  command[7:] in l:
				l.remove(command[7:])
		else:
			if command[6] == 'L':
				l.pop()
			else:
				l.pop(0)
for i in l[:-1]:
	print(i, end=' ')
print(l[-1])

### FIXED CODE ###

from collections import deque
n = input()
d = deque()
for i in range(int(n)):
	command = input()
	if command[0] == 'i':
		d.appendleft(command[7:])
	else:
		if command[6] == " ":
			if  command[7:] in d:
				d.remove(command[7:])
		else:
			if command[6] == 'L':
				d.pop()
			else:
				d.popleft()
for _ in range(len(d)-1):
	print(d.popleft(), end=" ")
print(d.pop())
### BUGGY CODE ###

K,S = map(int, input().split())


n = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k ==S:
                n=n+1
            else:
                n =n

print(n)


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline


K,S = map(int, input().split())
n = 0
up = math.floor(K)
for i in range(0,K+1):
    for j in range(0, K+1):
        if(0<= S-i-j <=K):
            n +=1
        else:
                n =n

print(n)
### BUGGY CODE ###

from math import factorial


def combination(n, r):  # n個からr個選ぶ場合の数
    if n < r:
        return 0
    else:
        return factorial(n)//(factorial(r) * factorial(n-r))


class UnionFind():
    def __init__(self, n):
        self.nodes = [-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root = root_x
                small_root = root_y
            else:
                small_root = root_x
                big_root = root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root] = big_root

    def solve_uncomfort(self, combi_n):
        sum = 0
        for n in self.nodes:
            if n < 0:
                n = abs(n)
                sum += combination(abs(n), 2)
        return combi_n-sum


def main():
    N, M = map(int, input().split())
    A, B = [], []
    for i in range(M):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    uf = UnionFind(N+1)
    get_root, unite, nodes = uf.get_root, uf.unite, uf.nodes
    ans = []
    combi_n = combination(N, 2)
    for i in reversed(range(M)):
        ans.append(uf.solve_uncomfort(combi_n))
        unite(A[i], B[i])
    print('\n'.join(map(str, ans[::-1])))


if __name__ == '__main__':
    main()


### FIXED CODE ###

N, M = map(int, input().split())
A = []
B = []
parent = [-1 for i in range(N)]
size = [1 for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)


def root(i):
    if parent[i] < 0:
        return i
    parent[i] = root(parent[i])
    return parent[i]


uncomfort = N * (N - 1) // 2
ans = [uncomfort]
for i in reversed(range(1, M)):
    # print(size)
    #print(parent, A[i], B[i])
    if root(A[i]) != root(B[i]):
        comfort = size[root(A[i])] * size[root(B[i])]
        uncomfort -= comfort
        #print(size[root(A[i])], size[root(B[i])])
        if size[root(A[i])] > size[root(B[i])]:
            size[root(A[i])] += size[root(B[i])]
            parent[root(B[i])] = root(A[i])
        else:
            size[root(B[i])] += size[root(A[i])]
            parent[root(A[i])] = root(B[i])
    # print(uncomfort)
    ans.append(uncomfort)
# print(ans[::-1])
for answer in reversed(ans):
    print(answer)
### BUGGY CODE ###

H,W = map(int, input().split())
from sys import stdin
field = []
bque = []
for i in range(H):
    st = stdin.readline()[:-1]
    ls = []
    for j,ss in enumerate(st):
        ls.append(ss)
        if ss=='#':
            bque.append([i,j])

    field.append(ls)

from collections import deque

que = deque([])
que.append(bque)
count = 0
while len(que)>0:
    ll = que.popleft()
    nls = []
    for item in ll:
        x = item[0]
        y = item[1]
        for dx in [-1,1]:
            for dy in [-1,1]:
                if 0<=x+dx<=H-1:
                    if field[x+dx][y]=='.':
                        field[x+dx][y]='#'
                        nls.append([x+dx,y])
                if 0<=y+dy<=W-1:
                    if field[x][y+dy]=='.':
                        field[x][y+dy]='#'
                        nls.append([x,y+dy])
    if len(nls) != 0:
        que.append(nls)
        count += 1
print(count)
"""微妙に遅かった60msぐらい　"""


### FIXED CODE ###

H,W = map(int, input().split())
from sys import stdin
field = []
bque = []
for i in range(H):
    st = stdin.readline()[:-1]
    ls = []
    for j,ss in enumerate(st):
        ls.append(ss)
        if ss=='#':
            bque.append([i,j])

    field.append(ls)

from collections import deque

que = deque([])
que.append(bque)
count = 0
while len(que)>0:
    ll = que.popleft()
    nls = []
    for item in ll:
        x = item[0]
        y = item[1]
        for dx in [-1,1]:
            for dy in [-1,1]:
                if 0<=x+dx<=H-1:
                    if field[x+dx][y]=='.':
                        field[x+dx][y]='#'
                        nls.append([x+dx,y])
                if 0<=y+dy<=W-1:
                    if field[x][y+dy]=='.':
                        field[x][y+dy]='#'
                        nls.append([x,y+dy])
    if len(nls) != 0:
        que.append(nls)
        count += 1
print(count)
"""微妙に遅かった60msぐらい　"""
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
c = 0
for i in range(n):
    c += all(p[i] <= p[j] for j in range(i))
print(c)


### FIXED CODE ###

import math
import copy

neko = 0
low = 10**6
n = int(input())
p = [int(x) for x in input().split()]
for i in range(n):
    if p[i]<low:
        neko += 1
    if p[i]<low:
        low = p[i]
print(neko)
### BUGGY CODE ###

import sys,collections
input = sys.stdin.readline

n = int(input())
l=[[]]
cnt = [0]*(n+1)
nn = []
for _ in range(n+1):
    l.append([])

for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
    nn.append(b)

m = max(map(len,l)) 

co = [ set(range(1,m+1)) for _ in range(n+1)]

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
l=[[]]
nn = []
for _ in range(n+1):
    l.append([])

for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
    nn.append(b)

ml = list(map(len,l)) 
m = max(ml)
co = []
for i in range(n+1):
    co.append( set(range(1,ml[i]+1) ))

col = [0]*(n+1)
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])
### BUGGY CODE ###

from itertools import permutations

def check(l1,l2,l3):
    count = 0
    for n2 in l2:
        for n1 in l1:
            if n1 > n2:
                break
            z = 2*n2 - n1
            for n3 in l3[::-1]:
                if n2 > n3:
                    break
                if n3 != z:
                    count += 1
    return count

N = int(input())
S = input()
Rlist, Glist, Blist = [],[],[]
for x in range(N):
    if S[x] == 'R':
        Rlist.append(x)
    elif S[x] == 'G':
        Glist.append(x)
    else:
        Blist.append(x)
    
ans = 0
for p in permutations([Rlist,Glist,Blist]):
    ans += check(p[0],p[1],p[2])
print(ans)

### FIXED CODE ###

N = int(input())
S = 'X' + input()

cnt_R, cnt_G, cnt_B = 0, 0, 0
for s in S[1:]:
    if s == 'R':
        cnt_R += 1
    elif s == 'G':
        cnt_G += 1
    elif s == 'B':
        cnt_B += 1

ans = cnt_R * cnt_G * cnt_B

for i in range(1,N-1):
    for j in range(i+1,N):
        k = 2*j - i
        if k > N:
            break
        
        a = S[i]; b = S[j]; c = S[k]
        if a != b and b != c and c != a:
            ans -= 1

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

import itertools
import collections

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

divided = collections.Counter(A_list)
ans = 0
for _, v in divided.items():
    ans += len(list(itertools.combinations(range(v), 2)))

for k in range(1, N + 1):
    n = divided[A_list[k - 1]]
    ans_k = ans
    if n > 1:
        ans_k -= n - 1

    print(int(ans_k))

### FIXED CODE ###

import collections
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

counts = collections.Counter(A_list)
ans = 0
for _, v in counts.items():
    # ans += len(list(itertools.combinations(range(v), 2)))
    if v > 1:
        ans += combinations_count(v, 2)

for k in range(1, N + 1):
    n = counts[A_list[k - 1]]
    ans_k = ans
    if n > 1:
        ans_k -= n - 1

    print(int(ans_k))
### BUGGY CODE ###

#dojkstra (prioroty queue ver.)
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

#lisの置換を全て作る
import math
def n_perm(lis):
    permed=[]
    ind=[i for i in range(len(lis))]
    for j in range(math.factorial(len(lis))):
        for i in range(len(ind)-2,-1,-1):
            if ind[i]<ind[i+1]:
                k=i
                break
        for i in range(len(ind)-1,k,-1):
            if ind[k]<ind[i]:
                l=i
                break
        ind[k], ind[l]=ind[l], ind[k]
        a=ind[k+1:]
        a.reverse()
        ind=ind[:k+1]+a
        permed.append([lis[i] for i in ind])
    return permed

#Warshall-Floyd
def w_f():
    inf=10**9
    d=[[inf]*V for i in range(V)]
    for i in range(V):
        d[i][i]=0

    for i in range(E):
        fr, to, co=map(int,input().strip().split(' '))
        d[fr-1][to-1]=co
        d[to-1][fr-1]=co
    for i in range(V):
        for j in range(V):
            for k in range(V):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d


dist=w_f()

rperm=n_perm(rlis)

ans=inf
for i in range(math.factorial(R)):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[i][j]-1][rperm[i][j+1]-1]
    ans=min(ans,a_tmp)
    
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#dojkstra
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[None] * V
for i in rlis:
    dist[i-1]=dijkstra(i-1)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)

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

import fractions
from functools import reduce
import collections

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n, m = map(int, input().split())
a = list(map(int, input().split()))
b =[]
v=[]
for i in range(n):
    b.append(a[i]*1.5)

x=lcm_list(a)


for i in range(n):
    for j in range(x//a[i]):
        v.append(a[i]*j+a[i]//2)

v = collections.Counter(v)
v=v.most_common()

if v[0][1]!=n:
    print(0)
else:
    print((m-v[0][0])//x+1)

### FIXED CODE ###

import fractions
from functools import reduce
import collections

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)



n, m = map(int, input().split())
a = list(map(int, input().split()))
a=set(a)
b=list(a)
n1=len(b)
count=0
v=[]

x=lcm_list(b)

for i in range(n1):
    while b[i]%2==0:
        b[i]=b[i]//2
        count+=1
    v.append(count)
    count=0

for i in range(n1-1):
    if v[i]!=v[i+1]:
        print(0)
        exit()

print((m-x//2)//x+1)
### BUGGY CODE ###

X, K, D = map(int, input().split())

ans = 1000000000000007
prev = 1000000000000007
if K % 2 == 0:
  i = K // 2
  for k in range(0, i+1):
    mn = abs(X + k * D * 2)
    if prev < mn:
      break
    prev = mn
    ans = abs(min(mn, ans))

  prev = 1000000000000007
  for k in range(0, i+1):
    mn = abs(X - k * D * 2)
    if prev < mn:
      break
    prev = mn
    ans = abs(min(mn, ans))

else:
  for k in range(1, K+1, 2):
    mn = abs(X + k * D)
    if prev < mn:
      break
    prev = mn
    ans = abs(min(mn, ans))

  prev = 1000000000000007
  for k in range(1, K+1, 2):
    mn = abs(X - k * D)
    if prev < mn:
      break
    prev = mn
    ans = abs(min(mn, ans))

print(ans)


### FIXED CODE ###

X,K,D = map(int,input().split())
 
if X<0:
    X *= -1
n = X//D
m = min(K,n)
 
X -= m*D
K -= m
if K%2:
    print(abs(X-D))
else:
    print(X)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(min(A),max(A)+1):
  cnt = 0
  if i in A:
    cnt += A.count(i)
  if i-1 in A:
    cnt += A.count(i-1)
  if i+1 in A:
    cnt += A.count(i+1)
  ans = max(ans,cnt) 
print(ans)
  

### FIXED CODE ###

n = int(input())
cnt = [0] * 100002
a = list(map(int, input().split()))
for v in a:
    cnt[v] += 1
    cnt[v+1] += 1
    cnt[v+2] += 1
    
print(max(cnt))