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

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if lst[0] == 1:
  if n > 1:
    if lst[0] == lst[1]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(2, lst[n - 1] // lst[i] + 1):
        if lst[i] * j in lst:
          tf_lst[lst[i] * j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)

### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        tf_lst[j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)
### BUGGY CODE ###

import numpy as np 
N = int(input())
A =list(map(int, input().strip().split()))
Ap = np.abs(A)
i = 0
m = 0
s = 0
M = 0
while i <= N - 1:
    if A[i] < 0:
        m += 1
    i += 1
if m % 2 == 0:
    M = np.sum(Ap)
if m % 2 == 1:
    while s <= N - 1:
        M1 = np.sum(Ap) - 2 * Ap[s]
        if M1 >= M:
            M = M1
        s += 1
print(M)

### FIXED CODE ###

import numpy as np 
N = int(input())
A =list(map(int, input().strip().split()))
Ap = np.abs(A)
i = 0
m = 0
s = 0
M = np.sum(Ap)
while i <= N - 1:
    if A[i] < 0:
        m += 1
    i += 1
if m % 2 ==0:
    print(M)
else:
    Ma = 0
    while s <= N - 1:
        M1 = M - 2 * Ap[s]
        if M1 >= Ma:
            Ma = M1
        s += 1
    print(Ma)
### BUGGY CODE ###

from operator import itemgetter
import heapq

N = int(input())
X = [[int(p) for p in input().split()] for _ in range(N)]

X.sort()
for i in range(N):
    X[i].append(i)
    
Y = sorted(X, key=itemgetter(1))

h = []
for i in range(N-1):
    heapq.heappush(h, (X[i+1][0]-X[i][0], i+1, i))
    heapq.heappush(h, (Y[i+1][1]-Y[i][1], Y[i+1][2], Y[i][2]))
    
    
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]
    
    
UF = UnionFind(N)
ans = 0
while h:
    t = heapq.heappop(h)
    if UF.isSameGroup(t[1], t[2]):
        continue
    ans += t[0]
    UF.unite(t[1], t[2])
    
print(ans)

### FIXED CODE ###

from operator import itemgetter
import heapq

N = int(input())
X = [[int(p) for p in input().split()] for _ in range(N)]

X.sort()
for i in range(N):
    X[i].append(i)
    
Y = sorted(X, key=itemgetter(1))

h = []
for i in range(N-1):
    heapq.heappush(h, (X[i+1][0]-X[i][0], i+1, i))
    heapq.heappush(h, (Y[i+1][1]-Y[i][1], Y[i+1][2], Y[i][2]))
    
    
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]
    
    
UF = UnionFind(N)
ans = 0
while h:
    t = heapq.heappop(h)
    if UF.isSameGroup(t[1], t[2]):
        continue
    ans += t[0]
    UF.unite(t[1], t[2])
    
print(ans)
### BUGGY CODE ###

N = int(input())

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

for k in range(1, N+1):
    ans = 0
    left = A[:k-1]
    right = A[k:]
    array = left + right
    
    array.sort()
    count = 1
    for i in range(N - 2):
        if array[i] == array[i+1]:
            count += 1
        else:
            ans += count*(count-1) // 2
            count = 1
    
    ans += count*(count-1) // 2
    print(ans)

### FIXED CODE ###

N_max = 2*(10**5)
N = int(input())

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

array = sorted(A)
quantity_of_num = [0]*(N_max + 1) # kという値がquantity_of_num[k]個あることを示す
type_index = list() # 文字の種類を昇順で記録していく配列。　len(type_index)が文字の種類数

count = 1 # 各文字が何個あるかの記録作業
for i in range(N-1):
    if array[i] == array[i+1]:
        count += 1
    else:
        type_index.append(array[i])
        quantity_of_num[array[i]] = count

        count = 1
type_index.append(array[i+1])
quantity_of_num[array[i+1]] = count

# type_index と　quantity_of_num の印字用
# for i in range(len(type_index)):
#     print(type_index[i], end="")
# print()
# for i in range(len(type_index)):
#     print(quantity_of_num[type_index[i]], end="")
# print()

total = 0 #k番目を除外せずに同じ数字の取り方が何通りあるかを検証
for i in range(len(type_index)):
        quantity = quantity_of_num[type_index[i]]
        # total の計算の挙動確認用
        # print("i = ", i, "quantitiy = ", quantity, "sum = ", quantity*(quantity - 1) // 2)
        total += quantity*(quantity - 1) // 2

for k in range(N):

    # k番目の数字から選んでいた部分を修正すれば良い
    # A[k] がk番目の数字
    quantity = quantity_of_num[A[k]]
    ans = total - ( quantity*(quantity-1) // 2) + ( (quantity-1)*(quantity-2) // 2)
    
    print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
p = 1
cnt = 0
for i in a:
        p*=i
while p % 2 == 0:
        p //=2
        cnt +=1
print(cnt)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p = 1
cnt = 0
for i in a:
        while i % 2 == 0:
                i //=2
                cnt +=1
print(cnt)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
S_set = list(set(S))
#print(S_set)
word_buf = []
cnt = []
mmax = -1
cnt.append(S.count(S_set[0]))
word_buf.append(S_set[0])
mmax = max(mmax,cnt[0])
for i in range(1,len(S_set)) :
    cnt.append(S.count(S_set[i]))
    if cnt[i] < mmax :
        pass
    elif cnt[i] == mmax :
        word_buf.append(S_set[i])
    else :
        word_buf.clear()
        word_buf.append(S_set[i])
    mmax = max(mmax,cnt[i]) # 現時点での最大値
word_buf = sorted(word_buf)
#print("--")
for i in range(len(word_buf)) :
    print(word_buf[i])

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [''] * N
for i in range(N) :
    S[i] = input()
S = Counter(S).most_common()
c = S[0][1]

print(*sorted([a for a,s in S if s==c]),sep="\n")
### BUGGY CODE ###

S = input()
ls_rem = []
for i in range(len(S)):
  p=int(S[i:len(S)])%2019
  ls_rem.append(p)
ls_rem.append(0)
from collections import Counter
C_rem = Counter(ls_rem)
ans=0
for i in C_rem.keys():
  n=C_rem[i]
  ans+=n*(n-1)/2
print(int(ans))  

### FIXED CODE ###

S = input()[::-1]

#aのMOD求めるンゴ
MOD=2019
ls_rem_a=[]
d=1
for i in range(len(S)):
  ls_rem_a.append(int(S[i])*d%MOD)
  d = d*10%MOD

#次に累積和求めるンゴ
ls_rem_s=[0]
sum=0
for i in range(len(S)):
  sum+=ls_rem_a[i]
  sum%=MOD
  ls_rem_s.append(sum)

#最後にMODが同じやつの個数を調べるンゴ
from collections import Counter
C_rem = Counter(ls_rem_s)
ans=0
for i in C_rem.keys():
  n=C_rem[i]
  ans+=n*(n-1)//2
print(ans)
### BUGGY CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N, W = MI()
inp = LI2(N)
w = [0]+[inp[i][0] for i in range(N)]
v = [0]+[inp[i][1] for i in range(N)]
dp = FILL2(INF,N+1,100001)
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(100001):
        if j-v[i] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
for j in range(100001):
    if dp[N][j] <= W:
        ans = j

print(ans)


### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.ones(N*1000+1, dtype=int) *(W+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    DP[v[i]:] = np.minimum(DP[:-v[i]]+ w[i], DP[v[i]:])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        ans = k
        
print(ans)
### BUGGY CODE ###

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

"""
ひとつ前だけ取っておく
"""

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

cur = prev = 'P'
for i in range(1, N+1):
    cur = prev = 'B' + prev + 'P' + prev + 'B'

print(cur[:X].count('P'))


### FIXED CODE ###

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

"""
解説参考
・必要な値を出してから再帰で場合分け
"""

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

# まず、それぞれのレベルについて全体の厚さとパティの枚数を求める
A = [1] * (N+1)
P = [1] * (N+1)
for i in range(1, N+1):
    A[i] = A[i-1] * 2 + 3
    P[i] = P[i-1] * 2 + 1

# レベルn、食べる厚さx
def dfs(n, x):
    # レベル0まで来て食べる厚さが残ってればパティ1枚
    if n == 0:
        if x >= 1:
            return 1
        else:
            return 0
    # ひとつ前の総数 + 左端バンズ = 真ん中のパティの手前まで
    if x <= A[n-1] + 1:
        # 前のレベルを調べる(食べる厚さは左端バンズを引く)
        return dfs(n-1, x-1)
    # 食べる厚さが真ん中のパティまでより多い
    else:
        # ひとつ前の総取り + 真ん中 + 前のレベルを調べる
        # (食べる厚さは前半のひとつ前の分と、左端バンズと真ん中パティを引く)
        # ※右端バンズを食べる場合でも、最終的にn == 0で1を返す時xの残数が1多いだけなので考慮しなくていい
        return P[n-1] + 1 + dfs(n-1, x-A[n-1]-2)

print(dfs(N, X))
### BUGGY CODE ###

n=int(input())
S=input()
s=list(S)
 
#print(s)
def jokyolist(s):
  jokyo=[]
  #jokyo配列はこれから除去すべき奴の番号のリスト
  for i in range(len(s)-1):
    if s[i]==s[i+1]:
      jokyo.append(i)
    jokyo=sorted(jokyo,reverse=True)
  return jokyo
 
def remov(s,jokyo):
  for i in range(len(jokyo)):
    s.pop(jokyo[i])
    return s

def removtimes(jokyo):
  t=len(jokyo)
  return t
 
i=0
while i<=n:
  jokyo=jokyolist(s)
  if removtimes(jokyo)==0:
    break
  s=remov(s,jokyo)
  i+=1

#print(s)
print(len(s))


### FIXED CODE ###

n=int(input())
S=input()
s=list(S)

p=[]
#print(s)
for i in range(n-1):
  if s[i]==s[i+1]:
    p.append(i)
p.sort(reverse=True)
l=len(p)

for i in range(l):
    #print(p[i])
    s.pop(p[i])

print(len(s))
### BUGGY CODE ###

def LCM(a,b):
  i = 2
  num_line_1 = [a]
  num_line_2 = [b]
  while(1):  
    num_line_1.append(num_line_1[0] * i)
    num_line_2.append(num_line_2[0] * i)
    
    for j in range(i):
      if num_line_1[j] in num_line_2:
        return num_line_1[j]        
    i += 1

num_line = [int(i) for i in input().split(" ")]
print(LCM(num_line[0], num_line[1]))

### FIXED CODE ###

def LMC(a,b):
  i = 1
  while(1):
    c = a * i
    if c % b == 0:
      return c
    i += 1

num_line = [int(i) for i in input().split(" ")]
print(LMC(num_line[0],num_line[1]))
### BUGGY CODE ###

from functools import reduce


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def gcd_n(numbers):
    return reduce(gcd, numbers)


def main():
    N, *A = map(int, open(0).read().split())
    print(max(gcd_n(A[:i] + A[i + 1:]) for i in range(N)))
    return


main()


### FIXED CODE ###

def gcd(a, b):
    if not a:
        # a が ゼロ ならば b
        return b
    if not b:
        # b が ゼロ ならば a
        return a
    while b:
        a, b = b, a % b
    return a


def main():
    N, *A = map(int, open(0).read().split())
    A.insert(0, 0)
    A.append(0)
    L = [0] * (N + 2)
    R = L[:]
    for i in range(1, N):
        L[i + 1] = gcd(L[i], A[i])
    for i in range(N, 0, -1):
        R[i] = gcd(R[i + 1], A[i])
    print(max(gcd(L[i], R[i + 1]) for i in range(1, N + 1)))
    return


main()
### BUGGY CODE ###

import sys
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
if n==1:
    if 1 in l:
        print(0)
    else:
        print(1)
    sys.exit()
ans1=0
ans2=0
if 1 in l:
    if 2 in l:
        print(0)
        sys.exit()
    else:
        ans2=1
else:
    ans1=1
    if 2 in l:
        pass
    else:
        ans2=2
ans=[0,ans1,ans2]
S=2
while S<n:
    S+=1
    if S in l:
        ans.append(0)
    else:
        ans.append((ans[-1]+ans[-2])%1000000007)
print(ans[-1])
#print(ans)

### FIXED CODE ###

import sys
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
if n==1:
    if 1 in l:
        print(0)
    else:
        print(1)
    sys.exit()
ans1=0
ans2=0
c=0
if 1 in l:
    c+=1
    if 2 in l:
        print(0)
        sys.exit()
    else:
        ans2=1
else:
    ans1=1
    if 2 in l:
        c+=1
    else:
        ans2=2
ans=[0,ans1,ans2]
S=2
while S<n:
    S+=1
    if c>=len(l):
        ans.append((ans[-1]+ans[-2])%1000000007)
    elif S==l[c]:
        c+=1
        ans.append(0)
    else:
        ans.append((ans[-1]+ans[-2])%1000000007)
print(ans[-1])
### BUGGY CODE ###

from fractions import gcd
k=int(input())
cnt=0
for i in range(1,k+1):
  for j in range(1,k+1):
    a=gcd(i,j)
    for k in range(1,k+1):
      cnt+=gcd(a,k)
print(cnt)

### FIXED CODE ###

from math import gcd
k=int(input())
cnt=0
for i in range(1,k+1):
  for j in range(1,k+1):
    a=gcd(i,j)
    for k in range(1,k+1):
      cnt+=gcd(a,k)
print(cnt)
### BUGGY CODE ###

N, K = map(int, input().split())
P = input().split()
P = [int(p) for p in P]

E = []
for p in P:
  E.append(p*(p+1)/2/p)
  
ans = 0.0
for i in range(K,N+1):
  if sum(E[i-K:i])> ans:
    ans = sum(E[i-K:i])
print(float(ans))

### FIXED CODE ###

N, K = map(int, input().split())
P = input().split()
P = [int(p) for p in P]

import numpy as np

E = (np.array(P)+1)/2
E = np.cumsum(E)  

ans = E[K-1]
for i in range(0,N-K):
  ans = max(ans, E[i+K]-E[i])
print(float(ans))
### BUGGY CODE ###


n=int(input())
s=input()
ans=0

for ii in range(1000):
    v = str(ii).zfill(3)
    #print(v[0])
    #s2=s
    #print("s=",v)
    start=0
    for j in range(3):
        f=0
        for i in range(start,n):
            if s[i] == v[j]:
                start=i+1
                f=1
                #print("aa",s2)
                break

        if f == 0 :
            break

    if f == 1:
        ans += 1
        #print(v)

print(ans)


### FIXED CODE ###

n=int(input())
s=input()
ans=0

for ii in range(1000):
    v = str(ii).zfill(3)
    start=0
    f=0
    
    for j in range(3):
        idx=s.find(v[j],start)
        if idx > -1:
            start = idx + 1
            f+=1
        else:
            break

    if f == 3:
        ans += 1

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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import collections
import heapq


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim?????§??????0?????????????°???¨?????¨????±???????
def compute_mst_prim(max_v, adj_list):
    # pred[u]?????????u???????????¨???????????????????????¨???
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # u??¨pred[u]????????¶???????????????key[u]?????\???
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # ??????????????????????????????????????\?????¨????????¨??????
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    while pq:
        _, u = heapq.heappop(pq)
        for v, v_cost in adj_list[u]:
            if v in (item[1] for item in pq):
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
    return (pred, key)


def main():
    max_v, max_e = map(int, input().split())
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections
import heapq


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim?????§??????0?????????????°???¨?????¨????±???????
def compute_mst_prim(max_v, adj_list):
    # pred[u]?????????u???????????¨???????????????????????¨???
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # u??¨pred[u]????????¶???????????????key[u]?????\???
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # ??????????????????????????????????????\?????¨????????¨??????
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # ????????????????????\?????????????????\??£???????????????????????????
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def main():
    max_v, max_e = map(int, input().split())
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))


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

import numpy as np

h, w, k = map(int, input().split())
s = np.array(
  [[int(s_ij) for s_ij in input()] for _ in range(h)],
  dtype=np.int)

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = np.zeros(h, dtype=np.int)
  cur_index = 0
  for i in range(1, h):
    if div_h & 1:
      cur_index += 1
    h_index[i] = cur_index
    div_h >>= 1
  white_choco = np.zeros(cur_index + 1, dtype=np.int)
  divide = 0
  j = 0
  while j < w:
    for i in range(h):
      if s[i, j]:
        if white_choco[h_index[i]] < k:
          white_choco[h_index[i]] += 1
        else:
          break
    else:
      j += 1
      continue
    white_choco[:] = 0
    divide += 1
  minimum = min(minimum, divide + cur_index)
print(minimum)

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [[int(s_ij) for s_ij in input()] for _ in range(h)]

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = [0] * h
  cur_index = 0
  mask = 1 << (h - 2)
  for i in range(1, h):
    if div_h & mask:
      cur_index += 1
    h_index[i] = cur_index
    mask >>= 1
  white_choco = [0] * (cur_index + 1)
  divide = 0
  j = 0
  flag = False
  while j < w:
    for i in range(h):
      white_choco[h_index[i]] += s[i][j]
    if max(white_choco) > k:
      if flag:
        break
      flag = True
      white_choco = [0] * (cur_index + 1)
      divide += 1
    else:
      j += 1
      flag = False
  else:
    minimum = min(minimum, divide + cur_index)
print(minimum)
### BUGGY CODE ###

#EDPC L
import sys
sys.setrecursionlimit(10**5)


def main():

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

    #dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

    dp=[[-1]*N for _ in range(N)]

    def rec(l,r):
        if dp[l][r]!=-1:
            return dp[l][r]
        
        if l==r:
            dp[l][r]=a[l]
            return dp[l][r]
        
        dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

        return dp[l][r]


    print(rec(0,N-1))
main()

### FIXED CODE ###

#EDPC L メモ化再帰じゃTLEで通らないのでやり直し

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

dp=[[-1]*N for _ in range(N)]

for k in range(N):
    dp[k][k]=a[k]

for r in range(1,N):
    for l in reversed(range(r)):
        dp[l][r]=max(a[l]-dp[l+1][r],a[r]-dp[l][r-1])

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


#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

N,W = map(int,input().split())
wv = int_mtx(N)

#f_inf = float("inf")
#dp = [f_inf]*N

# dp[i][w] = "番号 i 以下の商品でバッグの重さが w 以下になるように最適に詰めた場合"
dp = np.array([[0]*(W+1)]*(N+1))

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

for i in range(1,N+1):
    for w in range(wv[i-1][0],W+1):
        dp[i][w] = max(dp[i-1][w-wv[i-1][0]]+wv[i-1][1] , dp[i-1][w])
    dp[i,1:wv[i-1][0]] = dp[i-1,1:wv[i-1][0]]

print(dp[N][W])


### FIXED CODE ###

def e():
    import numpy as np

    N, W = map(int, input().split())

    dp = np.zeros(W+1, dtype=np.int64)

    for _ in range(N):
        w, v = map(int, input().split())
        np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

    print(dp[-1])


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

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	h = list(map(int, input().split()))
	# dpテーブル宣言: dp[今いる足場の番号-1]=最小コスト
	dp = [0] * N

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(1, N):
		for k in range(1, K+1):
			n_prev = n-k
			if n_prev >= 0:
				cost = abs(h[n] - h[n_prev]) + dp[n_prev]
				if dp[n]>0:
					dp[n] = min(dp[n], cost)
				else:
					dp[n] = cost
	print(dp[N-1])

resolve()

### FIXED CODE ###

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	# dpテーブル宣言: dp[今いる足場の番号-1]=[最小コスト, 足場の高さ]
	dp = [
		[float('inf'), int(h_)]
		for h_ in input().split()
	]
	dp[0][0] = 0
	dp[1][0] = abs(dp[0][1] - dp[1][1])

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(2, N):
		index_0 = max(0, n-K)
		h_ = dp[n][1]
		dp[n][0] = min(
			[
				abs( h_ - dp_[1] ) + dp_[0]
				for dp_ in dp[index_0:n]
			]
		)
	print(dp[N-1][0])

resolve()