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

#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
S = input()
ans = 0
for k in range(1,math.ceil(n/2)+1):
    if k <= ans or n-k <= ans:
        continue
    s = S[:k]
    t = S[k:]
    dp = [[0 for _ in range(n - k+1)] for _ in range(k+1)]
    for i in range(k):
        for j in range(n-k):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j+1],dp[i+1][j])
    ans = max(ans,dp[-1][-1])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = input()
dp = [[0]*(n+1) for _ in range(n+1)]
dp[-1][-1] = 1
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans,min(i-j,dp[i][j]))
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
py = []

od = [[]*1 for i in range(n)]
rank = [[]*1 for i in range(n)]

for i in range(0,m):
    p,y = map(int,input().split())
    py.append([p,y])
       
    odlen = len(od[p-1])
    if odlen >= 1 :

        low = 0
        high = odlen - 1
        mid = odlen//2

        while low <= high:
            mid = (low + high) >> 1
            guess = od[p-1][mid]
            if guess == y:
                break
            if guess > y :
                high = mid - 1
            else:
                low  = mid + 1        

        od[p-1].insert(low,y)

    else:
        od[p-1].append(y)

for i in range(0,m):
    r = od[py[i][0]-1].index(py[i][1])

    tmp = py[i][0]
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = py[i][0] // 10
    
    for j in range(6-digit):
        print('0',end="")
    print(py[i][0],end="")

    tmp = r + 1
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = r // 10

    for j in range(6-digit):
        print('0',end="")
    print(r+1)
 

### FIXED CODE ###

import sys as sys

lines =  input().split()
n = int(lines[0])
m = int(lines[1])

py = []
od = {}

#lines = sys.stdin.readlines()

for i in range(0,m):


    #l =  lines[i].split()
    l = input().split()
    p = int(l[0])
    y = int(l[1])
    
    if p in od :
        od[p].append([i,y])
    else:
        od[p] = [[i,y]]

a = []
for p in od.keys():
    od[p].sort(key=lambda x:x[1])
    r = 1

    for o in od[p]:
        cs = ""

        tmp = p
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10
        
        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(p)

        tmp = r 
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10

        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(r)        

        a.append([o[0],cs])
        r += 1

a.sort(key=lambda x:x[0])
for aa in a:
    print(aa[1])
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

s = ns()
b = [0]
k = 0
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*(10**k)
    n%=2019
    b.append(n)
    k+=1

import collections

c = collections.Counter(b)
ans = 0

for j in c.values():
    if j > 1:
        ans += j*(j-1)//2

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import defaultdict

s = ns()
d = defaultdict(int)
d[0] += 1
k = 1
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*k%2019
    n%=2019
    d[n] += 1
    k = (k*10)%2019

ans = 0

for j in d.values():
    if j > 1:
        ans += j*(j-1)//2

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

k, s = list(map(int, input().split()))
count = 0

for p in range(k+1):
    for q in range(min(k+1, s-p+1)):
        for r in range(min(k+1, s-p-q+1)):
            t = p + q + r
            if t == s:
                count += 1
                break
print(count)


### FIXED CODE ###

k, s = list(map(int, input().split()))
count = 0

for p in range(k+1):
    for q in range(k+1):
        r = s-p-q
        if r>=0 and r<=k:
            count += 1

print(count)
### BUGGY CODE ###

N = int(input())
h = list(input() for x in range(N))
a = []
c = 0
for i in range(0, N):
    if h[i] in a:
        c += 1
    else:
        a.append(h[i])
print(N - c)

### FIXED CODE ###

import collections

N = int(input())
h = list(input() for x in range(N))
c = collections.Counter(h)
print(len(c))
### BUGGY CODE ###

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

num= range(a,b+1)

d =0

for c in num:
  if c%x == 0:
    d+=1
  else:
    pass

print(d)

### FIXED CODE ###

a,b,x = map(int,input().split())
 
print(b//x-(a-1)//x)
### BUGGY CODE ###

h, w = map(int, input().split())
s = []
for i in range(h):
  t = input()
  s.append(t)
yokol = [[0 for i in range(w)] for j in range(h)]
yokor = [[0 for i in range(w)] for j in range(h)]
tateu = [[0 for i in range(w)] for j in range(h)]
tated = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
  cnt = 0
  for j in range(w):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      yokol[i][j] = cnt
  cnt = 0
  for j in reversed(range(w)):
    if s[i][j] == '#':
      cnt=0
    else:
      cnt += 1
      yokor[i][j] = cnt

for j in range(w):
  cnt = 0
  for i in range(h):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      tateu[i][j] = cnt
  cnt = 0
  for i in reversed(range(h)):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      tated[i][j] = cnt

ans = 0
for i in range(h):
  for j in range(w):
    x = yokol[i][j] + yokor[i][j] + tateu[i][j] + tated[i][j] - 3
    ans = max(ans,x)
print (ans)

### FIXED CODE ###

h, w = map(int, input().split())
s = []
for i in range(h):
  t = input()
  s.append(t)
yokol = [[0 for i in range(w)] for j in range(h)]
yokor = [[0 for i in range(w)] for j in range(h)]
tateu = [[0 for i in range(w)] for j in range(h)]
tated = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
  cnt = 0
  for j in range(w):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      yokol[i][j] = cnt
  cnt = 0
  for j in reversed(range(w)):
    if s[i][j] == '#':
      cnt=0
    else:
      cnt += 1
      yokor[i][j] = cnt

for j in range(w):
  cnt = 0
  for i in range(h):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      tateu[i][j] = cnt
  cnt = 0
  for i in reversed(range(h)):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      tated[i][j] = cnt

ans = 0
for i in range(h):
  for j in range(w):
    x = yokol[i][j] + yokor[i][j] + tateu[i][j] + tated[i][j] - 3
    ans = max(ans,x)
print (ans)
### BUGGY CODE ###

n=int(input())
ps=list(map(int,input().split()))
cnt=0
for i,p in enumerate(ps):
    if min(ps[:i+1])==p:
        cnt+=1
print(cnt)


### FIXED CODE ###

n=int(input())
ps=list(map(int,input().split()))
cnt=0
max_=ps[0]
min_=ps[0]
for p in ps:
    if min_>=p:
        cnt+=1
        min_=p
print(cnt)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())

C = sorted([R,G,B])
R = C[2]
G = C[1]
B = C[0]

ans = 0

for r in range(N//R + 1) :
    for g in range((N-r)//G + 1) :
        calc = r*R + g*G
        
        if (N-calc) < 0 :
            break
        
        if (N-calc) % B == 0 :
            ans += 1
print(ans)


### FIXED CODE ###

R,G,B,N = map(int,input().split())

ans = 0


for r in range(N+1) :
    
    for g in range(N+1) :
        if (N - (r*R + g*G)) < 0 : continue
        if (N - (r*R + g*G)) % B == 0 :
            ans += 1
            #print(r,g)
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
l = list(map(int, input().split()))
t = list(itertools.combinations(l, 3))

count = 0
for i in t:
    i_s = sorted(i)
    a,b,c = i_s
    if b <a+c and c<a+b:
        count+=1
print(count)



### FIXED CODE ###

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

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

N = int(input())
A = [int(input()) for _ in range(N)]
Pushed = [False]*N
Pushed[0] = True
i = 0
cnt = 0
while True:
    i = A[i] - 1
    cnt += 1
    if Pushed[i]:
        print(-1)
        break
    if i == 1:
        print(cnt)
        break


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
Pushed = [False]*N
Pushed[0] = True
i = 0
cnt = 0
while True:
    i = A[i] - 1
    cnt += 1
    if Pushed[i]:
        print(-1)
        break
    Pushed[i] = True
    if i == 1:
        print(cnt)
        break
### BUGGY CODE ###

# An efficient Python3 program to compute
# sum of bitwise OR of all pair

# Returns sum of bitwise OR
# of all pairs
def sumXOR( arr,  n):
    s = 0
    for i in range(0, 60):
        #  Count of zeros and ones
        zc = 0
        oc = 0
        # Individual sum at each bit position
        idsum = 0
        for j in range(0, n):
            if (arr[j] % 2 == 0):
                zc = zc + 1
            else:
                oc = oc + 1
            arr[j] = arr[j]  >> 1;
        # calculating individual bit sum
        idsum = oc * zc * (1 << i)
        # final sum
        s = (s + idsum)%(1000000007);
    return s



# driver function
s = 0
n = int(input())
arr = [int(i) for i in input().split()]
s = sumXOR(arr, n);
print(s)


### FIXED CODE ###

import numpy as np

MAX_DIGIT = 60
MOD = 10**9 + 7

N = int(input())
A = np.array([int(a) for a in input().split()])

answer = 0
for d in range(MAX_DIGIT + 1):
    A, r = (A>>1), A % 2
    s = int(r.sum())
    base = (1<<d) % MOD #this may be key
    answer += (base * s * (N - s)) % MOD

answer %= MOD
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
x = list(map(int, input().split()))
L = int(input())
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    ans = 1
    i = a
    d = 0
    while i < b:
        if d + x[i+1] - x[i] <= L:
            d += x[i+1] - x[i]
        else:
            ans += 1
            d = x[i+1] - x[i]
        i += 1
    print(ans)


### FIXED CODE ###

from bisect import bisect_right
import sys
input = sys.stdin.readline

N = int(input())
x = list(map(int, input().split()))
L = int(input())
log = 1
while 1 << log < N:
    log += 1
doubling = [[0] * (log + 1) for _ in range(N)]
for i in range(N):
    j = bisect_right(x, x[i] + L) - 1
    doubling[i][0] = j
for l in range(1, log + 1):
    for i in range(N):
        doubling[i][l] = doubling[doubling[i][l-1]][l-1]
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    ans = 0
    for l in range(log, -1, -1):
        if doubling[a][l] < b:
            ans += 1 << l
            a = doubling[a][l]
    print(ans + 1)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
dp=[[0]*(N+1) for i in range(N+1)]
#dp[a][b]でa:残っている数列の長さ b:左端
for w in range(1,N+1):
  for l in range(N-w+1):
    r=l+w
    dpl=-dp[l+1][r]+a[l]
    dpr=-dp[l][r-1]+a[r-1]
    dp[l][r]=max(dpl,dpr)
print(dp[0][N])

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
dp=[[0]*(N+1) for i in range(N+1)]
#dp[a][b]でa:残っている数列の長さ b:左端
for w in range(1,N+1):
  for l in range(N-w+1):
    r=l+w
    dpl=-dp[l+1][r]+a[l]
    dpr=-dp[l][r-1]+a[r-1]
    dp[l][r]=max(dpl,dpr)
print(dp[0][N])
### BUGGY CODE ###

import math
from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
used = [False] * (10**6+1)

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

input_list = sieve_of_erastosthenes(int(-(-10**3//1))+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

g = a[0]
arr = factorization(a[0])
for i in arr:
    used[i] = True

pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    arr = factorization(a[i+1])
    for i in arr:
        if i == 1: continue
        if used[i]: pair=False
        used[i] = True
if g > 1:
    print('not coprime')
    exit(0)
if not pair:
    print('setwise coprime')
    exit(0)
else:
    print('pairwise coprime')


### FIXED CODE ###

import math
import sys
import random

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

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

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

input_list = sieve_of_erastosthenes(10**6+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr
random.shuffle(a)
g = a[0]
arr = factorization(a[0])
used = set()
for i in arr:
    if i == 1: continue
    used.add(i)

# not coprimeか判定
for i in range(n-1):
    g = gcd(g, a[i+1])
if g > 1:
    print('not coprime')
    exit(0)

# pairwise coprimeか判定
used = [0] * (10**6+1)
pair = True
for _a in a:
    if _a == 1:
        continue
    if used[_a]:
        print('setwise coprime')
        exit(0)
    else:
        used[_a] = True

for p in prime_list:
    v = p
    cnt = 0
    while v < 10**6+1:
        if used[v]:
            cnt+=1
        v += p
    if cnt > 1:
        print('setwise coprime')
        exit(0)
print('pairwise coprime')
### BUGGY CODE ###

from collections import deque

n=int(input())
a_num = ord("a")
deque = deque()
deque.append(("a", a_num))
ans = []

while len(deque) > 0:
    s, s_num = deque.popleft()
    for i in range(a_num, s_num + 2):
        s_nxt = s + chr(i)
        s_num = max(s_num, i)
        if len(s_nxt) == n:
            ans.append(s_nxt)
        else:
            deque.appendleft((s_nxt, s_num))

ans.sort()
print(" ".join(ans))

### FIXED CODE ###

from collections import deque

n=int(input())
a_num = ord("a")
deque = deque()
deque.append(("a", a_num))
ans = []

if n > 1:
    while len(deque) > 0:
        s, s_num = deque.popleft()
        for i in range(a_num, s_num + 2):
            s_nxt = s + chr(i)
            s_num = max(s_num, i)
            if len(s_nxt) == n:
                ans.append(s_nxt)
            else:
                deque.appendleft((s_nxt, s_num))

    ans.sort()
    print(" ".join(ans))

else:
    print("a")
### BUGGY CODE ###

import bisect
import numpy as np
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = np.array([-(-i//a) for i in H])
ans = 0
for now in range(n):
  l = K[now]
  if l > 0:
    ans += l
    K[now:bisect.bisect_right(X, X[now]+2*d)] -= l
print(ans)

### FIXED CODE ###

import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = [-(-i//a) for i in H]
L = [0]*(n+2)
ans = 0
for i in range(n):
  L[i+1] += L[i]
  s = max(K[i]-L[i+1], 0)
  ans += s
  L[i+1] += s
  L[bisect.bisect_right(X, X[i]+2*d)+1] -= s
print(ans)
### BUGGY CODE ###

A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=[]
for i in range(len(B)-A[1]+1):
  D=0
  for j in range(A[1]):
    D=D+B[i+j]
  C.append(D)
print((max(C)+A[1])/2)



### FIXED CODE ###

A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=sum(B[0:A[1]])
D=C
for i in range(A[1]-1,A[0]-1):
  D=D+B[i+1]-B[i-A[1]+1]
  C=max(C,D)
print((C+A[1])/2)
### BUGGY CODE ###

from math import gcd
from functools import reduce
def gcds(*numbers):
  return reduce(gcd, numbers)
K = int(input())
ans = 0
for a in range(1, K + 1):
  for b in range(1, K + 1):
    for c in range(1, K + 1):
      ans += gcds(a, b, c)
print(ans)

### FIXED CODE ###

from math import gcd
from functools import reduce
def gcds(*numbers):
  return reduce(gcd, numbers)
K = int(input())
ans1 = 0
ans2 = 0
ans3 = 0
for a in range(1, K + 1):
  for b in range(a, K + 1):
    for c in range(b, K + 1):
      if a == b and b == c:
        ans1 += gcds(a, b, c)
      elif a == b or b == c or c == a:
        ans2 += gcds(a, b, c)
      else:
        ans3 += gcds(a, b, c)
print(ans1 + 3 * ans2 + 6 * ans3)
### BUGGY CODE ###

def main():
    import bisect

    N = int(input())
    upper = list(map(int, input().split()))
    middle = list(map(int, input().split()))
    lower = list(map(int, input().split()))

    upper.sort()
    middle.sort()
    lower.sort()

    cnt = 0

    index_mid = 0
    index_low = 0

    for i in range(N):
        len_up = upper[i]
        index_mid = index_mid + bisect.bisect_right(middle[index_mid:], len_up)

        if (index_mid >= N):
            break

        index_low = index_low + bisect.bisect_right(lower[index_low:], middle[index_mid])

        tmp_mid = index_mid
        tmp_low = index_low        

        while (tmp_mid < N):
            len_mid = middle[tmp_mid]
            tmp_low = tmp_low + bisect.bisect_right(lower[tmp_low:], len_mid)

            if (tmp_low < N):
                cnt += N - tmp_low
                tmp_mid += 1

            else:
                break

    print(cnt)


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    import bisect

    N = int(input())
    upper = list(map(int, input().split()))
    middle = list(map(int, input().split()))
    lower = list(map(int, input().split()))

    upper.sort()
    middle.sort()
    lower.sort()

    cnt = 0

    for i in range(N):
        mid = middle[i]
        index_up = bisect.bisect_left(upper, mid)
        index_low = bisect.bisect_right(lower, mid)
        
        cnt += index_up * (N - index_low)
    
    print(cnt)


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

N, W = map(int, input().split())
w = []
v = []
max_v = 1000
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
INF = int(1e9)*(N+1)
dp = [INF] * (max_v * N+1)
max_sum = max_v*N
dp[0] = 0

for i in range(N):
  for j in range(max_v*N,v[i]-1,-1):
    res = dp[j-v[i]]+w[i]
    if res > W: continue
    dp[j]=min(dp[j],res)

ans = 0
for i in range(max_v * N + 1):
    if dp[i] <= W:
        ans = max(ans, i)
print(ans)


### FIXED CODE ###

N, W = map(int, input().split())
w = []
v = []
max_v = 1000
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
INF = int(1e9)*(N+1)
dp = [[INF] * (max_v * N+1) for _ in range(N+1)]
max_sum = max_v*N
dp[0][0] = 0

for i in range(N):
    for j in range(max_v * N+1):
        if j+v[i] > max_sum:
            break
        dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]], dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(max_v * N + 1):
    if dp[N][i] <= W:
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h_list = list(map(int, input().split()))
dp = [float('INF') for i in range(N)]
dp[0] = 0

def update_dp(now, next):
  global h_list
  global dp
  global N
  if next > N - 1: return
  if dp[next] > dp[now] + abs(h_list[next] - h_list[now]):
    dp[next] = dp[now] + abs(h_list[next] - h_list[now])
  return

for i in range(N):
  for j in range(1, K + 1):
    update_dp(i, i + j)

print(dp[N - 1])

### FIXED CODE ###

N, K = map(int, input().split())
h_list = list(map(int, input().split()))
dp = [float('INF') for i in range(N)]
dp[0] = 0

def change_min(a, b):
  if a > b: return b
  else: return a

for i in range(N):
  for j in range(1, K + 1):
    if i + j > N - 1: continue
    dp[i + j] = change_min(dp[i] + abs(h_list[i] - h_list[i + j]), dp[i + j])

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

n, k = map(int, input().split())
while n >abs(k-n):
  n= abs(k-n)
print(n)

### FIXED CODE ###

n, k = map(int, input().split())
if n>k:
  n= n-(n//k)*k
while n >abs(k-n):
  n= abs(k-n)
print(n)
### BUGGY CODE ###


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


A=[int(i) for i in (input().split(" "))]



BC = [list(map(int,input().split())) for _ in range(M)]

for b,c in BC:
    count=0
    A.sort()
    for i in range(b):
        if c<A[i]:
            break
        else:
            A[i]=c
    
suma=0
#for i in A:
#    suma+=i

print(sum(A))

### FIXED CODE ###


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


A=[int(i) for i in (input().split(" "))]

A.sort()

BC = [list(map(int,input().split())) for _ in range(M)]

BC.sort(key=lambda x:x[1],reverse=True)

for b,c in BC:
    A.extend([c]*b)
    if len(A)>2*N:
        break

A.sort(reverse=True)
suma=0
#for i in A:
#    suma+=i

print(sum(A[:N]))
### BUGGY CODE ###

n,k = map(int,input().split())
num_lis = list(input().split())
max = 0
c = 0
for i in range(n):
    num_lis[i] = int(num_lis[i])
for i in range(n-k+1):
    for j in range(k):
        c = c + num_lis[i+j]/2 + 1/2
    if c > max:
        max = c
        c = 0
    else:
        c = 0
print(max)

### FIXED CODE ###

n,k = map(int,input().split())
num_lis = list(input().split())
max = 0
c = 0
for i in range(n):
    num_lis[i] = int(num_lis[i])
for i in range(n-k+1):
    if i == 0:
        for j in range(k):
            c = c + num_lis[i+j]/2 + 1/2
        max = c
    else:
        c = c - num_lis[i-1]/2 + num_lis[i+k-1]/2
        if c > max:
            max = c
print(max)