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

N,M=map(int,input().split())
A=list(map(int,input().split()))
tmp,count,l0=A[0],1,[]
for i in range(1,N):
  if tmp==A[i]:
    count+=1
  else:
    l0.append([tmp,count])
    tmp=A[i]
    count=1
l0.append([tmp,count])
BC=[]
for i in range(M):
  BC.append(list(map(int,input().split())))
BC.sort(key=lambda x:x[1],reverse=True)
cnt=0
l1=[]
for b,c in BC:
  if cnt>N:
    break
  else:
    l1.append([c,b])
    cnt+=b
l=l0+l1
l.sort(key=lambda x:x[0],reverse=True)
d=0
ans=0
while d<N:
  if l[0][1]==0:
    l.remove(l[0])
  ans+=l[0][0]
  d+=1
  l[0][1]-=1
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[]
for i in range(M):
  BC.append(list(map(int,input().split())))
A.sort(reverse=True)
BC.sort(key=lambda x:x[1],reverse=True)
ans=sum(A)
for i in range(M):
  for _ in range(BC[i][0]):
    if A==[]:
      print(ans)
      exit()
    if A[-1]>BC[i][1]:
      print(ans)
      exit()
    else:
      p=A.pop()
      ans-=p
      ans+=BC[i][1]
      
print(ans)
### BUGGY CODE ###

#template
def inputlist(): return [int(k) for k in input().split()]
#template
H,W = inputlist()
graph = [0]*H
for i in range(H):
    graph[i] = list(input())
from collections import deque
que = deque()
seen = [[False]*W for _ in range(H)]
li = []
for x in range(H):
    for y in range(W):
        if graph[x][y] == '#':
            tp = (x,y)
            li.append(tp)
que.append(li)
dx = [1,0,-1,0]
dy = [0,1,0,-1]
count = 0
while len(que) != 0:
    l = que.popleft()
    lis = []
    for tup in l:
        xa = tup[0]
        ya = tup[1]
        for i in range(4):
            nx = xa + dx[i]
            ny = ya + dy[i]
            if nx >= H or ny >= W or nx < 0 or ny < 0:
                continue
            if graph[nx][ny] == '#':
                continue
            graph[nx][ny] = '#'
            lis.append((nx,ny))
    count+=1
    if len(lis) == 0:
        print(count-1)
        exit()
    que.append(lis)


### FIXED CODE ###

#template
def inputlist(): return [int(k) for k in input().split()]
#template
H,W = inputlist()
graph = [0]*H
for i in range(H):
    graph[i] = list(input())
from collections import deque
que = deque()
seen = [[False]*W for _ in range(H)]
li = []
for x in range(H):
    for y in range(W):
        if graph[x][y] == '#':
            tp = (x,y)
            li.append(tp)
que.append(li)
dx = [1,0,-1,0]
dy = [0,1,0,-1]
count = 0
while len(que) != 0:
    l = que.popleft()
    lis = []
    for tup in l:
        xa = tup[0]
        ya = tup[1]
        for i in range(4):
            nx = xa + dx[i]
            ny = ya + dy[i]
            if nx >= H or ny >= W or nx < 0 or ny < 0:
                continue
            if graph[nx][ny] == '#':
                continue
            graph[nx][ny] = '#'
            lis.append((nx,ny))
    count+=1
    if len(lis) == 0:
        print(count-1)
        exit()
    que.append(lis)
### BUGGY CODE ###

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

for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
c = collections.Counter(a)
for i in range(1,n+1):
    print(c[i])
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    K, S = LI()

    ans = 0
    for x, y, z in itertools.product(range(K + 1), repeat=3):
        if x + y + z == S:
            ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    K, S = LI()

    ans = 0
    for x, y in itertools.product(range(K + 1), repeat=2):
        if 0 <= S - (x + y) <= K:
            ans += 1

    print(ans)

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

N=int(input())

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

rcnt=0
length=len(A)

for i in range(length):
    cnt=0
    for j in range(length):
        if A[i]%A[j]!=0 and A[i]!=A[j]:
            cnt+=1
    if cnt==N-1:
        rcnt+=1
print(rcnt)

### FIXED CODE ###

#青の人の解答（hir35）

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

#それぞれの数字が何回ずつ出現したかをカウント
c = Counter(a)

#リストpに10＾6+1個のTrueを格納
p = [True] * (10 ** 6 + 1)

#list(set())で重複したものを取り除いてからリストにできる
s = list(set(a))

#sの要素一つ一つを見ていく
for x in s:
    t = x * 2
    #tが10^6以下ならば，p[t]にFalseを代入
    #つまり，x(aに格納されている数)の倍数がfalseに
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0

for x in a:
    #もしその数が一つしかなくて，倍数がないならans+1
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]

ab_d={a*(10**6)+b for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[[2 for _ in [0]*5] for _ in [0]*5]
    for i in range(5):
        for j in range(5):
            if 0<a+i-2<=h and 0<b+j-2<=w:
                if (a+i-2)*(10**6)+b+j-2 in ab_d:
                    temp[i][j]=1
                else:
                    temp[i][j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[i+k][j+l] for k in range(3) for l in range(3)]
            if 2 not in cnt:
                ans[sum(cnt)-1].add((a+i-2)*(10**6)+b+j-2)
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)

### FIXED CODE ###

h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d={a*(10**9)+b-1 for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[None for _ in [0]*25]
    for i in range(5):
        for j in range(5):
            if 0<a+i-2<=h and 0<b+j-2<=w:
                if (a+i-2)*(10**9)+b+j-3 in ab_d:
                    temp[i*5+j]=1
                else:
                    temp[i*5+j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
            if None not in cnt:
                ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

import copy

N=int(input())
X=list(map(int,input().split(" ")))
Y=copy.deepcopy(X)
Y.sort()
Y1=Y[:N//2]
Y2=Y[N//2:]
a=Y[N//2]
b=Y[N//2-1]
for i in X:
  if i in Y1:
    print(a)
  else:
    print(b)

### FIXED CODE ###

import copy

N=int(input())
X=list(map(int,input().split(" ")))
Y=copy.deepcopy(X)
Y.sort()
a=Y[N//2]
b=Y[N//2-1]
for i in X:
  if i<=b:
    print(a)
  else:
    print(b)
### BUGGY CODE ###

n = int(input())
l = []
for i in range(n):
  a, b = map(int, input().split())
  l.append((a, b))
  
l = sorted(l, key=lambda x: x[1], reverse=True)
s = sum(j for j, _ in l)
for i in range(n):
  if s > l[0][1]:
    print("No")
    exit()
  else:
    a = l.pop(0)
    s -= a[0]
print("Yes")

### FIXED CODE ###

n = int(input())
l = []
s = 0
for i in range(n):
  a, b = map(int, input().split())
  s += a
  l.append((a, b))
  
l = sorted(l, key=lambda x: x[1])
for i in range(n):
  if s > l[-1][1]:
    print("No")
    exit()
  else:
    a = l.pop()[0]
    s -= a
print("Yes")
### BUGGY CODE ###

class unionfind:
	def __init__(self, n):
		self.parent = list(range(n))
	def find(self, i):
		if self.parent[i] != i: self.parent[i] = self.find(self.parent[i])
		return self.parent[i]
	def unite(self, i, j):
		i = self.find(i)
		j = self.find(j)
		if i != j: self.parent[i] = j
	def issame(self, i, j):
		return self.find(i) == self.find(j)
	def groups(self):
		r = range(len(self.parent))
		return [[j for j in r if self.issame(j, i)] for i in r if i == self.parent[i]]
	@staticmethod
	def isconnected(l, u = None):
		nw, nh = len(l), len(l[0])
		rw, rh = range(nw), range(nh)
		if not u: u = unionfind(nw * nh)
		f = -1
		for i in rw:
			for j in rh:
				if not l[i][j]: continue
				if f < 0: f = i + j * nw
				if j > 0 and l[i][j] == l[i][j - 1]: u.unite(i + j * nw, i + j * nw - nw)
				if i > 0 and l[i][j] == l[i - 1][j]: u.unite(i + j * nw, i + j * nw - 1)
		return f >= 0 and all([u.issame(f, i + j * nw) for i in rw for j in rh if l[i][j]])
	@staticmethod
	def isconnectedlist(nw, nh, lst):
		l = [[False] * nw for j in range(nh)]
		for i, j in lst: l[i][j] = True
		return unionfind.isconnected(l)

def culc(x):
    return int(x * (x-1) //2)

N , M = map(int, input().split())
ans_lst = []
lst = []
for i in range(M):
    A , B = map( int , input().split())
    lst.append([A , B] )
cu = unionfind(N)
maxroute = culc(N)
for ls  in  reversed(lst):
    temp = maxroute
    for subg in cu.groups():
        temp -= culc(len(subg))
    ans_lst.append(temp)
    cu.unite(ls[0]-1 , ls[1]-1)

for y in reversed(ans_lst):
    print(y)

### FIXED CODE ###

#学習用
def root(x):
    # xが根であれば
    if x == p[x]:
        # xを返す
        return x
    # xが根でなければp[x]の根をp[x]に設定する
    p[x] = y = root(p[x])
    # p[x]の根を返却する
    return y
def unite(x, y):
    # xとyの根を取得する
    px = root(x); py = root(y)
    # xとyの根が同じならば
    if px == py:
        # 根が同じならば、0を返す
        return 0
    # yの根がxの根より大きければ、
    if px < py:
        # yの根の位置のp[]を、xの根にする
        p[py] = px
        # xの根の位置のサイズszを、yの根の位置のサイズだけ加算する
        sz[px] += sz[py]
    else:
    # yの根がxの根より小さければ
        # xの根の位置のp[]を、yの根を指すようにする
        p[px] = py
        sz[py] += sz[px]
    # 根が異なっていた＝結合した場合は、1を返却する
    return 1

N , M = map(int, input().split())
*p , = range(N)
sz = [1] * N
E = []
for i in range(M):
    a , b = map(int, input().split())
    E.append((a-1, b-1))

ans = [None] * M
E.reverse()
res = 0
ans[-1] = "%d\n" % (N*(N-1)//2)

for i , (a,b) in enumerate(E[:-1]):
    sa = sz[root(a)]; sb = sz[root(b)]
    if unite(a , b):
        sc = sz[root(a)]
        res += sc*(sc-1)//2 - sa*(sa-1)//2 - sb*(sb-1)//2
    ans[-2-i] = "%d\n" % (N*(N-1)//2 -res)
open(1, 'w').writelines(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = [tuple(map(int,input().split())) for _ in range(q)]
for i in range(q):
  temp = list(reversed(s[lr[i][0]-1:lr[i][1]]))
  cnt = 0
  while len(temp) > 1:
    x = temp.pop()
    y = temp[-1]
    if x == 'A' and y == 'C':
      cnt += 1
  print(cnt)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()

ac = [0] * (n - 1)
for i in range(n-1):
  if s[i] == 'A' and s[i+1] == 'C':
    ac[i] = 1

acc = [0] * n
for i in range(n-1):
  acc[i+1] = acc[i] + ac[i]

lr = [tuple(map(int,input().split())) for _ in range(q)]
for i in range(q):
  l = lr[i][0] - 1
  r = lr[i][1] - 1
  print(acc[r] - acc[l])
### BUGGY CODE ###

dbg = False

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

if a > b:
    x, y = a, b
else:
    x, y = b, a

for i in range(1, int((y+1)/2)+1):
    if y % i == 0:
        gcd_tmp = int(y / i)
        if dbg: print(gcd_tmp)
        if x % gcd_tmp == 0:
            print(gcd_tmp)
            exit()

print(1)

### FIXED CODE ###

dbg = False

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

if a > b:
    x, y = a, b
else:
    x, y = b, a

divs = [1]
for i in range(1, int((y+1)/2)+1):
    gcd_tmp = int(y / i)
    if dbg: print('%d, %d' % (i, gcd_tmp))
    if i > gcd_tmp:
        break
    if y % i == 0:
        if x % gcd_tmp == 0:
            print(gcd_tmp)
            exit()
        elif x % i == 0:
            divs.append(i)

print(max(divs))
### BUGGY CODE ###

a,b,c,k=map(int,input().strip().split())
if k==0:
    if abs(a-b)>10**18:
        print('Unfair')
    else:
        print(a-b)
else:
    for i in range(k):
        x=b+c 
        y=a+c 
        z=a+b 
        a=x
        b=y
        c=z
    if abs(x-y)>10**18:
        print('Unfair')
    else:
        print(x-y)






### FIXED CODE ###

a,b,c,k=map(int,input().strip().split())
if k%2==0:
    print(a-b)
else:
    print(-(a-b))
### BUGGY CODE ###

def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    score = [0] * n

    """
        assert get_answer(["4 3",
                       "1 3", "1 4", "2 3",
                       "2 10", "1 100", "3 1"]) == "100 111 101 100"
    """
    t_index = {}
    for i in range(1, n + 1):
        t_index[i] = []
    for nn in n_data:
        t_index[nn[0]].append(nn[1])
        t_index[nn[1]].append(nn[0])

    q_index = {}
    for qq in q_data:
        i = qq[0]
        if i in q_index.keys():
            q_index[i] += qq[1]
        else:
            q_index[i] = qq[1]

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        if i in q_index.keys():
            s += q_index[i]
        score[i - 1] += s
        t_stack += t_index[i]
        for si in range(len(t_index[i])):
            s_stack.append(s)

    s_value = str(score[0])
    for i in range(1, n):
        s_value += " " + str(score[i])
    return s_value


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))


### FIXED CODE ###

import collections

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1): #木グラフの隣接リストを作成
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
for _ in range(q): #各頂点についてcount[v]を計算
 v,val=map(int,input().split())
 cnt[v]+=val
q=collections.deque()
q.append(1) #DFSのスタックによる実装、まずスタックに始点1を積む
checked=[0]*(n+1) #各頂点を見たかどうかのフラグを持っておく
while q:
 v=q.pop()
 checked[v]=1 #頂点を見たかどうかのフラグを更新する
 for u in g[v]:
   if checked[u]==1: #vの子ノードuについて、まだ見ていない頂点であればcount[u]をcount[u]+=count[v]として更新する
     continue
   cnt[u]+=cnt[v]
   q.append(u) #スタックに子ノードuを積む
print(*cnt[1:]) #各頂点のcountが答えとなる
### BUGGY CODE ###

n, k = map(int, input().split())
h = [0] + list(map(int, input().split())) + [0]
INF = 10 ** 18

def solve(i, nokori):
    if i == 0:
       return 0
    res = INF
    for j in range(nokori + 1):
        if i - 1 - j < 0:
            break
        diff = max(h[i] - h[i - 1 - j], 0)
        res = min(solve(i - 1 - j, nokori - j) + diff, res)
    return res

print(solve(n + 1, k))

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**18

k = n - k

dp = [[INF]*(k+1) for i in range(n+1)]
dp[0][0] = 0

# i番目のブロックを必ず選ぶ
for i in range(n):
    # すでにj回選んでいる
    for j in range(k):
        if j == 0:
            dp[i+1][j+1] = min(dp[0][j] + h[i], dp[i+1][j+1])
            continue
        #最後に選んだブロックはlast_i番目
        for last_i in range(i):
            if last_i + 1 < j:
                continue
            dp[i+1][j+1] = min(dp[last_i+1][j] + max(h[i] - h[last_i], 0), dp[i+1][j+1])

ans = 10**18
for i in range(n+1):
    ans = min(dp[i][k], ans)

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

#!/usr/bin/env python3
import sys


def solve(N: int):
    for i in range(1, 3501):
        for j in range(i, 3501):
            z = 4*i*j - N*j - N*i
            if z != 0:
                h, r = divmod((N*i*j), z)
                if r == 0 and 0 <= h:
                    print(h, i, j)
                    exit()
            

    return

N = int(input())
solve(N)


# # Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
# def main():
#     def iterate_tokens():
#         for line in sys.stdin:
#             for word in line.split():
#                 yield word
#     tokens = iterate_tokens()
#     N = int(next(tokens))  # type: int
#     solve(N)

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


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int):
    for i in range(1, 3501):
        for j in range(i, 3501):
            z = 4*i*j - N*(j+i)
            if z > 0:
                h, r = divmod((N*i*j), z)
                if r == 0:
                    print(h, i, j)
                    exit()
            

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


# #!/usr/bin/env python3
# n = int(input())
# for i in range(1, 3501):
#   for j in range(1, 3501):
#     seed = 4 * i * j - n * (i + j) 
#     if seed > 0:
#       k, mod = divmod(n * i * j, seed) 
#       if mod == 0:
#         print(i, j, k)
#         exit()
### BUGGY CODE ###

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

for i in range(q):
    start = lr[i][0]-1
    end = lr[i][1]-1
    ans = 0
    for j in range(start,end):
        if s[j] == 'A':
            if s[j+1] == 'C':
                ans += 1
    print(ans)

### FIXED CODE ###

n,q=[int(i) for i in input().split()]
s = input()
qs = []
for i in range(q):
    qs.append([int(i) for i in input().split()])

counts = [0] * n
count = 0
for i in range(1,n):
    if s[i] == "C" and s[i-1] == "A":
        count += 1
    counts[i] = count
counts = [0] + counts


for i in range(q):
    st, en = qs[i]
    print(counts[en] - counts[st])
### BUGGY CODE ###

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

import os
import sys

input()
nums = input().split()
answer = 0
temp = 0

for i in range(len(nums)):
    for j in nums[i:]:
        temp = temp + int(j)
        if temp == 0:
            answer = answer + 1
    temp = 0

print(answer)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
import math

lenums = int(input())
nums = [int(i) for i in input().split()]
answer = 0

dp = [0]

for i in range(lenums):
    dp.append(dp[i] + nums[i])

count_dict = collections.Counter(dp)
for i in count_dict.values():
    if i <= 1:
        continue
    answer = answer + i * (i - 1) // 2 # xC2

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

n = int(input())
c = str(input())
cn = [False]*n
for i in range(n):
    if c[i]=="R":
        cn[i]= True


ans = 0
k=n-1
b=0

for i in range(n):
    if b==1:
        break

    if cn[i]== False:
        for j in range(k,0,-1):

            if cn[j]==True:
                k =j
                if i < j:
                    cn[i]=True
                    cn[j]=False
                    ans +=1
                    break
                elif i>=j:
                    b=1
                    break
print(ans)

### FIXED CODE ###

n = int(input())
c = str(input())
cn = [False]*n
for i in range(n):
    if c[i]=="R":
        cn[i]= True


ans = 0
k=n-1
b=0

for i in range(n):
    if b==1:
        break

    if not(cn[i]):
        for j in range(k,0,-1):

            if cn[j]:
                k =j-1
                if i < j:
                    #cn[i]=True
                    #cn[j]=False
                    ans +=1
                    break
            if i>=j:
                b=1
                break
print(ans)
### BUGGY CODE ###

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

dp = [0 for _ in range(n)]
for i in range(1, n):
    hi = h[i]
    x = 2 * 10 ** 9
    for j in range(1, min(k, i) + 1):
        x = min(x, dp[i - j] + abs(hi - h[i - j]))
    dp[i] = x
print(dp[-1])


### FIXED CODE ###

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

dp = [0 for _ in range(n)]
for i in range(1, n):
    hi = h[i]
    x = 2 * 10 ** 9
    for j in range(1, min(k, i) + 1):
        x = min(x, dp[i - j] + abs(hi - h[i - j]))
    dp[i] = x
print(dp[-1])
### BUGGY CODE ###

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

nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1

for i in range(2,n+1):
  if i not in a: nums[i] = nums[i-1] + nums[i-2]
  else: nums[i] = 0
print(nums[n]%(10**9+7))


### FIXED CODE ###

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

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0
  
for i in range(2, n+1):
  if i in a:
    continue
  dp[i] = dp[i - 1] + dp[i - 2]
  dp[i] %= inf
  
print(dp[n])
### BUGGY CODE ###

N , K = map(int,input().split())
h = list(map(int,input().split()))

def dp(cost):
    for x in range(1,N):
        for k in range(max(x-K,0),x):
            cost[x] = min(cost[x] , cost[k] + abs( h[x] - h[k] ) )
        # cost[x] =  min( [ cost[k] + abs( h[x] - h[k] ) for k in range(max(x-K,0),x) ] ) 
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

N , K = map(int,input().split())
h = list(map(int,input().split()))

def dp(cost):
    for x in range(1,N):
        for k in range(max(x-K,0),x):
            cost[x] = min(cost[x] , cost[k] + abs( h[x] - h[k] ) )
        # cost[x] =  min( [ cost[k] + abs( h[x] - h[k] ) for k in range(max(x-K,0),x) ] ) 
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

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

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

cnt = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                cnt += 1
print(cnt) 

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
  for y in range(k+1):
    if 0 <= (s-x-y) <= k:
      cnt+=1
print(cnt)
### BUGGY CODE ###

n=int(input())
li = list(map(int,input().split()))
an=[]

for i in range(1,n+1):
    an.append(li.index(i)+1)

print(*an)

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
an=[0]*n

for i in range(n):
    an[li[i]-1]=i+1

print(*an)
### BUGGY CODE ###

x = int(input())

s =[2]
a = x

if x==2:
    print(x)
else:
  for i in range(3,x,2):
    if all(i%k!=0 for k in s):
        s.append(i)
        
  for t in range(x,2*x):
    if all(t%k!=0 for k in s):
      print(t)
      exit()






### FIXED CODE ###

x = int(input())

s =[2]

if x==2:
    print(x)
    exit()
else:
    for i in range(3,int(x/2),2):
        if all(i%k!=0 for k in s):
            s.append(i)

while any(x%k==0 for k in s):
  x+=1
else:
  print(x)
### BUGGY CODE ###

N, W = [int(_) for _ in input().split()]
dp = [0] * (W + 10)  # [[0] * 3 for _ in range(10 ** 5 + 2)]

for i in range(1, N + 1):
    w, v = [int(_) for _ in input().split()]
    for j in range(len(dp) - 1, -1, -1):
        if j + w <= W:
            dp[j + w] = max(dp[j + w], dp[j] + v)

print(max(dp))


### FIXED CODE ###

N, W = [int(_) for _ in input().split()]
dp = [0] * (W + 10)  # [[0] * 3 for _ in range(10 ** 5 + 2)]

for i in range(1, N + 1):
    w, v = [int(_) for _ in input().split()]
    for j in range(len(dp) - 1, -1, -1):
        if j + w <= W:
            dp[j + w] = max(dp[j + w], dp[j] + v)

print(max(dp))