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

import sys
input = sys.stdin.readline

import bisect

def main():
    n = int(input())
    s = []

    for i in range(n):
        a = int(input())
        i = bisect.bisect_left(s, a)
        if len(s) > i and s[i] == a:
            s.remove(a)
        else:
            s.insert(i, a)


    print(len(s))


main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect

def main():
    n = int(input())
    s = []

    for i in range(n):
        a = int(input())
        i = bisect.bisect_left(s, a)
        if len(s) > i and s[i] == a:
            s.remove(a)
        else:
            s.insert(i, a)


    print(len(s))


main()
### BUGGY CODE ###

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

dp = [0] * n
dp[1] = abs(h[0] - h[1])
for i in range(2, n):
  dp[i] = min(dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, k + 1) if i - j >= 0)
print(dp[-1])

### FIXED CODE ###

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

dp = [0] * n
dp[1] = abs(h[0] - h[1])
for i in range(1, n):
  dp[i] = min(dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, k + 1) if i - j >= 0)
print(dp[-1])
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int,input().split()))

ans = 10**20 * -1
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break

        now = t
        if tot > 0:
            e = (K - (i + 1)) // l
            now += tot * e
        ans = max(ans, now)
print(ans)



### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int,input().split()))

ans = 10**20 * -1
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break

        now = t
        if tot > 0:
            e = (K - (i + 1)) // l
            now += tot * e
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h, w = li()
grid = [lc() for _ in range(h)]

# 左側の照らせるマス
left = [[0]*w for _ in range(h)]
for row in range(h):
    cur = 0
    for col in range(w-1, -1, -1):
        if grid[row][col] == ".":
            cur += 1
            left[row][col] = cur
        else:
            cur = 0

# 右側の照らせるマス
right = [[0]*w for _ in range(h)]
for row in range(h):
    cur = 0
    for col in range(w):
        if grid[row][col] == ".":
            cur += 1
            right[row][col] = cur
        else:
            cur = 0

# 上側の照らせるマス
up = [[0]*w for _ in range(h)]
for col in range(w):
    cur = 0
    for row in range(h-1, -1, -1):
        if grid[row][col] == ".":
            cur += 1
            up[row][col] = cur
        else:
            cur = 0

# 下側の照らせるマス
down = [[0]*w for _ in range(h)]
for col in range(w):
    cur = 0
    for row in range(h):
        if grid[row][col] == ".":
            cur += 1
            down[row][col] = cur
        else:
            cur = 0

# 最大値
ans = 0
for row in range(h):
    for col in range(w):
        ans = max(ans, left[row][col] + right[row][col] + up[row][col] + down[row][col])

print(ans-3)


### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


h, w = li()
grid = [lc() for _ in range(h)]


lr = [[0]*w for _ in range(h)]
tb = [[0]*w for _ in range(h)]

for row in range(h):
    for col in range(w):
        if col == 0:
            lr[row][col] = 1 if grid[row][col] == "." else 0

        else:
            if grid[row][col] == "#":
                continue

            else:
                lr[row][col] = lr[row][col-1] + 1

for row in range(h):
    for col in range(w-2, -1, -1):
        if lr[row][col] == 0:
            continue
        else:
            lr[row][col] = max(lr[row][col+1], lr[row][col])

for col in range(w):
    for row in range(h):
        if row == 0:
            tb[row][col] = 1 if grid[row][col] == "." else 0

        else:
            if grid[row][col] == "#":
                continue
            else:
                tb[row][col] = tb[row-1][col] + 1

for col in range(w):
    for row in range(h-2, -1, -1):
        if tb[row][col] == 0:
            continue
        else:
            tb[row][col] = max(tb[row+1][col], tb[row][col])

ans = 0
for row in range(h):
    for col in range(w):
        ans = max(ans, lr[row][col] + tb[row][col])

print(max(0, ans-1))
### BUGGY CODE ###

string=list(input())
N=len(string)
num=[0]*(N+1)
sum0=0
if string==[">"]:
     sum0=1
else:
     for i in range(N):
          if string[i]=="<":
               num[i+1]=num[i]+1
          else:
               if num[i]==0:
                    num[i+1]=0
                    for j in range(N):
                         num[i-j]+=1
                         if ((i-j-2)<0 or string[i-j-2]=="<"):
                              if num[i-j-1]<=num[i-j]:
                                   num[i-j-1]=num[i-j]+1
                              break
     sum0=0
     for i in range(N+1):
          sum0=sum0+num[i]
print(sum0)

### FIXED CODE ###

S = input()
N = len(S)+1
a = [0] * N
for i in range(N-1):
	if S[i] == '<':
		a[i+1] = max(a[i+1], a[i]+1)
for i in range(N-2, -1, -1):
  if S[i] == '>':
    a[i] = max(a[i], a[i+1]+1)
      
print(sum(a))
### BUGGY CODE ###

from numpy import array
n=int(input())
s=input()
t=s.count("E")
r=s.count("W")
dp =[r-(s[-1]=="W")]+[0 for i in range(n-1)]
dp2=[t-(s[0 ]=="E")]+[0 for i in range(n-1)]

for i in range(1,n):
    if s[i]=="W":
        dp2[i]=dp2[i-1]
    else:
        dp2[i]=dp2[i-1]-1
    if s[::-1][i]=="E":
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]-1
print(min(array(dp[::-1])+array(dp2)))

### FIXED CODE ###

from numpy import*
n=int(input())
s=input()
x=[0]+[1 if i=="W" else 0 for i in s]
del x[-1]
y=[1 if i=="E" else 0 for i in s]
print(min(array(cumsum(x))+s.count("E")-array(cumsum(y))))
### BUGGY CODE ###

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

b = []
ap = b.append

for i in range(n):
  ap(a[i])
  b.reverse()

print(' '.join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = input().split()

if n & 1:
  print(' '.join(a[::-2]+a[1::2]))
else:
  print(' '.join(a[-1:0:-2]+a[::2]))
### BUGGY CODE ###

n, k = map(int, input().split())
s = input()
x = [0]
for si in s:
    if si == '1':
        if x[-1] >= 0:
            x[-1] += 1
        else:
            x.append(1)
    else:
        if x[-1] <= 0:
            x[-1] -= 1
        else:
            x.append(-1)
y = []
for i in range(len(x)):
    yi = 0
    ki = 0
    for j in range(i, len(x)):
        if x[j] > 0:
            yi += x[j]
        else:
            if ki >= k:
                break
            yi += -x[j]
            ki += 1
    y.append(yi)
    if ki < k:
        break
print(max(y))


### FIXED CODE ###

n, k = map(int, input().split())
s = input()
x = [0]
for i in range(n - 1):
    if s[i:i + 2] in ['01', '10']:
        x.append(i + 1)
y = []
for i in range(len(x)):
    idx = i + 2 * k
    if s[x[i]] == '0':
        if i > 0:
            continue
    else:
        idx += 1

    if idx < len(x):
        y.append(x[idx] - x[i])
    else:
        y.append(n - x[i])
        break
print(max(y))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split(' ')]

order = []

for attendance in range(N):
    A = [x - 1 for x in A]
    order.append(str(A.index(0) + 1))

print(" ".join(order))

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split(' ')]

order = sorted(range(len(A)), key=lambda k: A[k])
order = [str(x + 1) for x in order]

print(" ".join(order))
### BUGGY CODE ###

import copy
import collections

n = int(input())
list1 = list(map(int,input().split()))
list2 = collections.Counter(list1)
list3 = copy.copy(list1)

kei1=0
kei2=0

for j in list2.values():
    kei1 += j * (j-1) // 2

for x in range(n):
    list3 = copy.copy(list1)
    k = list3.pop(x)
    if k in list3:
        kei2 = list3.count(k)

    print(kei1-kei2)

### FIXED CODE ###

import collections

n = int(input())
list1 = list(map(int,input().split()))
list2 = collections.Counter(list1)

kei1=0

for j in list2.values():
    kei1 += j * (j-1) // 2

for x in list1:
    print(kei1 - (list2[x] -1))
### BUGGY CODE ###

K = int(input())

lis = []
val = -1
num = 0
tens = 1
for i in range(1, 10 ** 6 + 1):
  num += 7 * tens
  if num % K == 0:
    print(i)
    exit()
  tens *= 10

### FIXED CODE ###

K = int(input())

x = 7 % K

for i in range(1, K + 8):
  if x == 0:
    print(i)
    exit()
  
  x = (10 * x + 7) % K
  
print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(2)
    exit()

es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7
dp = [[1,1] for i in range(N)]

def rec(i,parent):
    for to in es[i]:
        if to==parent: continue
        rec(to,i)
        dp[i][0] *= (dp[to][0] + dp[to][1])
        dp[i][1] *= dp[to][0]
        dp[i][0] %= MOD
        dp[i][1] %= MOD

rec(0,-1)
print(sum(dp[0])%MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
MOD = 10**9+7

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

dp = [[1,1] for i in range(N)]
def rec(v,p=-1):
    for to in es[v]:
        if to==p: continue
        rec(to,v)
        dp[v][0] *= (dp[to][0] + dp[to][1])
        dp[v][1] *= dp[to][0]
        dp[v][0] %= MOD
        dp[v][1] %= MOD
rec(0)

print(sum(dp[0]) % MOD)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
K = 0
S = 0
T = []
if sum(A) < sum(B):
    print('-1')
else:
    for i in range(N):
        if A[i] < B[i]:
            K += 1
            S = S + B[i] - A[i]
        elif A[i] > B[i]:
            T.append(A[i] - B[i])
        else:
            continue
    while S > 0:
        S -= max(T)
        T.remove(max(T))
        K += 1
    print(K)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
K = 0
S = 0
T = []
if sum(A) < sum(B):
    K = -1
else:
    for i in range(N):
        if A[i] < B[i]:
            K += 1
            S = S + B[i] - A[i]
        elif A[i] > B[i]:
            T.append(A[i] - B[i])
        else:
            continue
T.sort()
L = 0
while S > L:
    L += T.pop()
    K += 1
print(K)
### BUGGY CODE ###

from itertools import permutations

N, C = map(int,input().split())
D = []
for _ in range(C):
    D.append(list(map(int,input().split())))
c = []
for _ in range(N):
    c.append(list(map(int,input().split())))

ans = 10 ** 8
for L in permutations([i for i in range(C)], 3):
    if len(set(L)) != 3:
        continue
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += D[c[i][j]-1][L[(i+j)%3]]
    ans = min(ans, cnt)

print(ans)

### FIXED CODE ###

from collections import defaultdict
from itertools import permutations

N, C = map(int,input().split())
D = []
for _ in range(C):
    D.append(list(map(int,input().split())))
c = []
for _ in range(N):
    c.append(list(map(int,input().split())))

P = [defaultdict(int) for _ in range(3)]
for i in range(N):
    for j in range(N):
        P[(i+j)%3][c[i][j]-1] += 1

ans = float('inf')
for L in permutations([i for i in range(C)], 3):
    cnt = 0
    for i in range(3):
        for j in range(C):
            cnt += P[i][j] * D[j][L[i]]
    ans = min(ans, cnt)

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

A,B=map(int,input().split())
C=B-A
now=A
XOR=A
for i in range(C):
    XOR=XOR^(now+1)
    now+=1
print(XOR)

### FIXED CODE ###

#D問題
A,B = map(int,input().split())
def f(n):
    if n%2 == 0:
        if (n//2)%2 == 0:
            return n
        else:
            return n+1
    else:
        if ((n-1)//2)%2 == 0:
            return 1
        else:
            return 0
        
FB = f(B)
FA = f(A-1)
print(FB^FA)
### BUGGY CODE ###

import heapq
def dijkstra(graph, size, start, r):
    distance = [float('inf')] * size
    distance[start] = 0
    que = []
    heapq.heappush(que, (0, start))
    while len(que):
        _, u = heapq.heappop(que)
        for length, vi in graph[u]:
            if distance[vi] > distance[u] + length[r]:
                distance[vi] = distance[u] + length[r]
                heapq.heappush(que, (distance[vi], vi))
    return distance

import sys
f = sys.stdin

import collections

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    graph = collections.defaultdict(list)
    for ai, bi, cost, time in abct:
        graph[ai].append(((cost, time), bi))
        graph[bi].append(((cost, time), ai))
        
    k = int(f.readline())
    for i in range(k):
        p, q, r = map(int, f.readline().split())
        dist = dijkstra(graph, m + 1, p, r)
        print(dist[q])

### FIXED CODE ###

import heapq
import sys
from collections import defaultdict

def dijkstra(graph, size, start):
    d = [float('inf')] * size
    d[start] = 0
    q = [(0, start)]
    while len(q):
        du, u = heapq.heappop(q)
        for length, v in graph[u]:
            if d[v] > du + length:
                d[v] = du + length
                heapq.heappush(q, (d[v], v))
    return d

f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [map(int, f.readline().split()) for _ in range(n)]
    d = [defaultdict(list), defaultdict(list)]
    
    for ai, bi, ci, ti in abct:
        ai -= 1
        bi -= 1
        d[0][ai].append((ci, bi))
        d[0][bi].append((ci, ai))
        d[1][ai].append((ti, bi))
        d[1][bi].append((ti, ai))
    
    dist = {}
    for i in range(int(f.readline())):
        p, q, r = map(int, f.readline().split())
        p -= 1
        q -= 1
        try:
            print(dist[(q,r)][p])
        except KeyError:
            try:
                print(dist[(p,r)][q])
            except:
                dist[(p,r)] = dijkstra(d[r], m, p)
                print(dist[(p,r)][q])
### BUGGY CODE ###

s = str(input())
t = str(input())

ls = list(s)
lt = list(t)

ans = 0
while True:
  rep_cnt = 0
  for i in range(0, len(ls)):
    if ls[i] != lt[i]:
      ls[i] = lt[i]
      rep_cnt += 1
      break
  if rep_cnt > 0:
    ans += rep_cnt
  else:
    break

print(str(ans))



### FIXED CODE ###

s = str(input())
t = str(input())

ls = list(s)
lt = list(t)

ans = 0
j = 0
while True:
  rep_cnt = 0
  for i in range(j, len(ls)):
    j += 1
    if ls[i] != lt[i]:
      ls[i] = lt[i]
      rep_cnt += 1
      break
  if rep_cnt > 0:
    ans += rep_cnt
  else:
    break

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

from collections import deque
n=input()
r=[map(int,raw_input().split()) for _ in xrange(n)]
m=input()
pa=[map(int,raw_input().split()) for _ in xrange(m)]
for i in xrange(m):
    d=[1]*n
    q=deque([pa[i][0]])
    used=[False]*n
    used[pa[i][0]-1]=True
    while len(q)!=0:
        f=0
        p=q.popleft()
        p-=1
        if d[p]==pa[i][2]:continue
        for j in r[p][2:]:
            j-=1
            if pa[i][1]-1==j:
                f=1
                d[j]+=d[p]
                break
            if used[r[j][0]-1]:continue
            q.append(j+1)
            d[j]=d[p]+1
            used[j]=True
        if f==1:
            break
    if f==1:
        print(d[j])
    else:
        print("NA")

### FIXED CODE ###

n=int(raw_input())
g=[[1000000]*n for _ in xrange(n)]
for i in xrange(n):
    g[i][i]=0
for i in xrange(n):
    r=map(int,raw_input().split())
    for j in r[2:]:
        g[r[0]-1][j-1]=1
for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
m=int(raw_input())
for i in xrange(m):
    s,d,v=map(int,raw_input().split())
    s-=1
    d-=1
    if g[s][d]<v:
        print(g[s][d]+1)
    else:
        print('NA')
### BUGGY CODE ###

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

#まず一つ答えをつくる これはたぶん貪欲でいける
days=[]
i=0
while i<N:
    if S[i]=='o':
        days.append(i)
        i+=C
    if len(days)>=K:
        break
    i+=1

def check(plan):
    cnt=0
    ii=0
    while ii<N:
        if plan[ii]=='o':
            cnt+=1
            ii+=C
        if cnt>=K:
            break
        ii+=1
    if cnt>=K:
        return True
    else:
        return False

p=S
for i in days:
    p[i]='x'
    if not check(p):
        print(i+1)
    p[i]='o'

### FIXED CODE ###

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

maekara=[]
i=1
cnt=0
while i<=N and cnt<K:
    if S[i-1]=='o':
        maekara.append(i)
        i+=C+1
        cnt+=1
    else: i+=1

usirokara=[]
j=N
cnt=0
while j>=1 and cnt<K:
    if S[j-1]=='o':
        usirokara.append(j)
        j-=C+1
        cnt+=1
    else: j-=1
usirokara=usirokara[::-1]

for i in range(K):
    if maekara[i]==usirokara[i]:
        print(maekara[i])
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i] != s[j]:
            if (s[i]+s[j]).count('R') == 0:
                cnt += s[j+1:n].count('R')
                if 2*j-i <= n-1:
                    if s[2*j-i] == 'R':
                       cnt -= 1
            elif (s[i]+s[j]).count('G') == 0:
                cnt += s[j+1:n].count('G')
                if 2*j-i <= n-1:
                    if s[2*j-i] == 'G':
                       cnt -= 1
            else:
                cnt += s[j+1:n].count('B')
                if 2*j-i <= n-1:
                    if s[2*j-i] == 'B':
                       cnt -= 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count('R')*s.count('G')*s.count('B')
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i] != s[j]:
            if 2*j-i > n-1:
                break
            if s[2*j-i] not in(s[i],s[j]):
                cnt -= 1
print(cnt)
### BUGGY CODE ###

from itertools import combinations

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

patterns = set(map(lambda c: ''.join(c), combinations(S, 3)))
print(len(patterns))

### FIXED CODE ###

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

count = 0
for i in range(1000):
    password = str(i).zfill(3)
    j = 0
    for s in S:
        if s == password[j]:
            j += 1
            if j == 3:
                count += 1
                break
print(count)
### BUGGY CODE ###

n = int(input())
v = list(map(int, input().split()))
a = v[::2]
b = v[1::2]
count = 0
count1 = 0
for i in a:
    count = max(count, a.count(i))
for j in b:
    count1 = max(count1, b.count(j))
print(n//2 if len(set(v)) == 1 else n-count-count1)

### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int, input().split()))
a = Counter(v[::2])
b = Counter(v[1::2])
count = a.most_common()
count1 = b.most_common()
if len(set(v)) == 1:
    print(n//2)
    exit()
if count[0][0] == count1[0][0]:
    print(n- count[0][1] - (max(count[1][1], count1[1][1])))

else:
    print(n - count[0][1] - count1[0][1])
### BUGGY CODE ###

n = list(map(int, input().split()))
N = n[0]
M = n[1]
X = []
Y = []
for i in range(M):
    a = list(map(int, input().split()))
    X.append(a[0])
    Y.append(a[1])
v=0
w=0
z=[X[0],Y[0]]
while v==0:
    for i in range(1,M):
        if z[0]<=Y[i] and z[1]>=X[i]:
            z[0]=max(z[0],X[i])
            z[1]=min(z[1],Y[i])
        else:
            v=1
            w=1
        if i==M-1:
            v=1
if w==0:
    print(z[1]-z[0]+1)
else:
    print(0)





### FIXED CODE ###

n = list(map(int, input().split()))
N = n[0]
M = n[1]
X = []
Y = []
for i in range(M):
    a = list(map(int, input().split()))
    X.append(a[0])
    Y.append(a[1])
v=0
w=0
x=max(X)
y=min(Y)
if y>=x:
    print(y-x+1)
else:
    print(0)
### BUGGY CODE ###

N = int(input())
power = 1
for i in range(N):
    power *= (i + 1)

print(power % (10 ** 9 + 7))


### FIXED CODE ###

N = int(input())
power = 1
for i in range(N):
    power *=  (i + 1) 
    power = power % (10 ** 9 + 7)

print(power)
### BUGGY CODE ###

from heapq import heappush, heappop

def main():
    INF = float("inf")

    N, *S = map(int, open(0).read().split())

    S.sort(reverse=True)

    P = [S[0]]
    S[0] = INF
    for _ in range(N):
        Q = P[:]
        while Q:
            q = heappop(Q)

            for i, s in enumerate(S):
                if s < q:
                    heappush(P, s)
                    S[i] = INF
                    break
            else:
                print("No")
                quit()

    print("Yes")


main()


### FIXED CODE ###

INF = float("inf")

N, *S = map(int, open(0).read().split())
M = len(S)

S.sort(reverse=True)

Q = [S[0]]
S[0] = INF
for _ in range(N):
    Q.sort()
    T = Q[:]

    cur = 1
    while Q:
        p = Q.pop()
        while S[cur] >= p:
            cur += 1
            if cur == M:
                print("No")
                exit()
        T.append(S[cur])
        S[cur] = INF

    Q = T

print("Yes")
### BUGGY CODE ###

H, N = list(map(int, input().split()))
AB = [[None,None]]
for i in range(N):
  AB.append(list(map(int, input().split())))

dp = [int(1e8) for i in range(H+1)]
dp[0] = 0

for h in range(1,H+1):
  cand = [dp[0] + AB[n][1] if h - AB[n][0] < 0 else dp[h-AB[n][0]] + AB[n][1]for n in range(1,N+1) ]
  dp[h] = min(cand)
print(dp[H])

### FIXED CODE ###

import sys

input = sys.stdin.readline
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

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

import sys
sys.setrecursionlimit(300000)
from collections import Counter

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


S = input()

m = [0]
for i in range(len(S)):
    m.append((m[-1] + int(S[- i - 1]) * (10 ** i)) % 2019)


ans = 0
for cnt in Counter(m).values():
    ans += cnt * (cnt - 1) // 2
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from collections import Counter

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


S = input()

m = [0]
pow = 1
for i in range(len(S)):
    m.append((m[-1] + int(S[- i - 1]) * pow) % 2019)
    pow = (pow * 10) % 2019


ans = 0
for cnt in Counter(m).values():
    ans += cnt * (cnt - 1) // 2
print(ans)
### BUGGY CODE ###

def main():
  N, K = map(int,input().split())
  H = list(map(int,input().split()))

  dp = [1e9]*N
  dp[0] = 0
  for i in range(N):
    for j in range(1,K+1):
      if i+j < N:
        dp[i+j] = min(dp[i+j], dp[i]+abs(H[i]-H[i+j]))
      else:
        break
  print(dp[N-1])

if __name__ == "__main__":
  main()

### FIXED CODE ###

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

dp = [1e9]*N
dp[0] = 0
for i, b in enumerate(H):
  if i != 0:
    x = max(0, i-K)
    dp[i] = min([abs(b-d)+p for d, p in zip(H[x:i], dp[x:i])])
print(dp[-1])