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

import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
      
def fun(S1,S2,n,m):
    if n == 0 or m == 0:
        return ""
    dp = list2d(n+1,m+1,"")
    for i in range(1,n+1):
        for j in range(1,m+1):
            if S1[i-1] == S2[j-1]:
                dp[i][j] = dp[i-1][j-1] + S1[i-1]
            else:
                a = dp[i-1][j]
                b = dp[i][j-1]
                if len(a) > len(b):
                    dp[i][j] = a
                else:
                    dp[i][j] = b
    return dp[n][m]
    

S1 = input()
S2 = input()
n = len(S1)
m = len(S2)
print(fun(S1,S2,n,m))

### FIXED CODE ###

import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
      
def fun(A,B,m,n,dp):
    for i in range(1,m+1):
        for j in range(1,n+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    return dp
                
def longestsub(A,B):
    m = len(A)
    n = len(B)
    if m==0 or n==0:
        return ""
    temp = [0]*(n+1)
    dp = [temp.copy() for i in range(m+1)]
    d = fun(A,B,m,n,dp)
    i= m;j = n;Ans = ""
    while i>0 and j>0:
        if A[i-1] == B[j-1]:
            Ans += A[i-1]
            i-=1;j-=1
        else:
            a = d[i][j-1] ; b =d[i-1][j]
            if a > b:
                j-=1
            else:
                i-=1
    return Ans[::-1]

A = input()
B = input()
print(longestsub(A,B))
### BUGGY CODE ###

def main():
    import sys
    import time
    from collections import deque
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N = int(input())
    P = [int(a) for a in input().strip().split()]
    G = [[min(n, N-n-1,i, N-i-1) for i in range(N)] for n in range(N)]
    Gflag = [[1] * N for _ in range(N)]
    ans = 0

    vecs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    for p in P:
        row, col = (p-1) // N, (p-1) % N
        ans += G[row][col]
        Gflag[row][col] = 0
        q = deque([(G[row][col], row, col)])
        while q:
            cost, row, col = q.popleft()
            if row > 0:
                if G[row-1][col] > cost + Gflag[row][col]:
                    G[row-1][col] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row-1, col))
            if row < N-1:
                if G[row+1][col] > cost + Gflag[row][col]:
                    G[row+1][col] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row+1, col))
            if col > 0:
                if G[row][col-1] > cost + Gflag[row][col]:
                    G[row][col-1] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row, col-1))
            if col < N-1:
                if G[row][col+1] > cost + Gflag[row][col]:
                    G[row][col+1] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row, col+1))

    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import time
    from collections import deque
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N = int(input())
    P = [int(a) for a in input().strip().split()]
    G = [[min(n, N-n-1,i, N-i-1) for i in range(N)] for n in range(N)]
    Gflag = [[1] * N for _ in range(N)]
    ans = 0

    vecs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    for p in P:
        row, col = (p-1) // N, (p-1) % N
        ans += G[row][col]
        Gflag[row][col] = 0
        q = deque([(G[row][col], row, col)])
        while q:
            cost, row, col = q.popleft()
            if row > 0:
                if G[row-1][col] > cost + Gflag[row][col]:
                    G[row-1][col] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row-1, col))
            if row < N-1:
                if G[row+1][col] > cost + Gflag[row][col]:
                    G[row+1][col] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row+1, col))
            if col > 0:
                if G[row][col-1] > cost + Gflag[row][col]:
                    G[row][col-1] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row, col-1))
            if col < N-1:
                if G[row][col+1] > cost + Gflag[row][col]:
                    G[row][col+1] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row, col+1))

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

N = int(input())
pairs = []
answer = 0
def StartEnd(x):
    start = str(x)[0]
    end = str(x)[-1]
    return int(start), int(end)

for i in range(1, N+1):
    pair = ()
    a, b = StartEnd(i)
    pair += (a, b)
    pairs.append(pair)
    
for i in range(N):
    p = pairs[i]
    q = p[::-1]
    answer += pairs.count(q)
    
print(answer)    



### FIXED CODE ###

N = int(input())
numMap = {}
answer = 0
def StartEnd(x):
    start = str(x)[0]
    end = str(x)[-1]
    return start, end

for i in range(1, N+1):
    # print('numMap:', numMap)
    pair = StartEnd(i)
    if pair in numMap:
        numMap[pair] += 1
    else:
        numMap[pair] = 1

for i in range(1, N+1):
    key = StartEnd(i)
    rev = key[::-1]
    # print('rev:', rev)
    if rev in numMap:
        answer += numMap[rev]
    
print(answer)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())

s = [[] for _ in range(h)]
dis = [[-1] * w for _ in range(h)]

for i in range(h):
    s[i] = input()

white_cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white_cnt += 1

q = deque()
q.append([0, 0, 1])  # x,y,d

while len(q) > 0:
    x, y, d = q.popleft()
    dis[y][x] = d
    dxy = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    for dx, dy in dxy:
        nx = x + dx
        ny = y + dy
        if 0 > nx or w <= nx or 0 > ny or h <= ny:
            continue
        if dis[ny][nx] != -1 or s[ny][nx] == "#":
            continue
        q.append([nx, ny, d + 1])

if dis[h - 1][w - 1] == -1:
    print(-1)
else:
    print(white_cnt - dis[h - 1][w - 1])



### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())

s = [[] for _ in range(h)]
dis = [[-1] * w for _ in range(h)]

for i in range(h):
    s[i] = input()

white_cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white_cnt += 1

q = deque()
q.append([0, 0, 1])  # x,y,d
dis[0][0] = 1

while len(q) > 0:
    x, y, d = q.popleft()
    dxy = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    for dx, dy in dxy:
        nx = x + dx
        ny = y + dy
        if 0 > nx or w <= nx or 0 > ny or h <= ny:
            continue
        if dis[ny][nx] != -1 or s[ny][nx] == "#":
            continue
        q.append([nx, ny, d + 1])
        dis[ny][nx] = d + 1

if dis[h - 1][w - 1] == -1:
    print(-1)
else:
    print(white_cnt - dis[h - 1][w - 1])
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
for i in range(n):
    y = x[:]
    y.pop(i)
    y = list(sorted(y))
    s = n // 2
    print(y[-s])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x[:])
for i in x:
    s = n // 2
    ss= y[-s]
    if i >= ss:
        print(y[-(s+1)])
    else:
        print(y[-s])
### BUGGY CODE ###

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

i_range = [int(x) for x in range(1, N-1)]
j_range = [int(x) for x in range(2, N)]
k_range = [int(x) for x in range(3, N+1)]

val = 0


"""
for k in k_range:
    for j in j_range:
        for i in i_range:
            judge = ""
            if( (j-i == k-j) or (i >= j) or (j >= k)):
                print("(i, j, k) = ({}, {}, {}) break".format(i, j, k))
                break
            if((S[i-1] != S[j-1]) and (S[j-1] != S[k-1]) and (S[i-1] != S[k-1])):
                val = val + 1
                judge = "〇"
            else:
                judge = "×"
            print("(i, j, k) = ({}, {}, {}) -> ({}, {}, {}) {}".format(i, j, k, S[i-1], S[j-1], S[k-1], judge))
"""


for k in k_range:
    for j in j_range:
        if(j >= k):
            break
        for i in i_range:
            if(i >= j):
                break
            if((S[i-1] != S[j-1]) and (S[j-1] != S[k-1]) and (S[i-1] != S[k-1])):
                if(j-i != k-j):
                    judge = "〇"
                    val = val + 1
                else:
                    judge = "×"
            #print("(i, j, k) = ({}, {}, {}) -> ({}, {}, {}) {}".format(i, j, k, S[i-1], S[j-1], S[k-1], judge))

print(val)

### FIXED CODE ###

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


"""
脳死で全探索で探すとO(n^3）で時間がかかる。
→1つめの条件で予め絞った後に、そこからさらに絞り込むやり方をやる。（補集合を引くパターン）
j-i=k-jを満たすもの（すなわちk=2j-i）を求めて、あとで引き算すればOK.
≠は＝で考えて引き算のほうがよい。
"""

r_count = S.count('R')
g_count = S.count('G')
b_count = S.count('B')


val = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        k = 2*j-i
        if(k < N):
            if((S[i] != S[j]) and (S[j] != S[k]) and (S[i] != S[k])):
                val += 1

print((r_count * g_count * b_count) - val)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = list(int(input()) for _ in range(q))

for i in range(n):
    ans = "Yes" if q - a.count(i+1) < k else "No"
    print(ans)


### FIXED CODE ###

from collections import Counter
n, k, q = map(int, input().split())
a = list(int(input()) for _ in range(q))
mycounter = Counter(a)
for i in range(n):
    ans = "Yes" if q - mycounter[i+1] < k else "No"
    print(ans)
### BUGGY CODE ###

N = int(input())
X = [list(map(int,input().split(' '))) for i in range(N)]
if (abs(X[0][0])+abs(X[0][1]))%2 == 0:
    flag = True
else:
    flag = False

flag2 = True
X_D = []
for i in range(len(X)):
    X_D.append(abs(X[i][0])+abs(X[i][1]))
    if flag:
        if X_D[i]%2 == 1:
            flag2 = False 
    else:
        if X_D[i]%2 == 0:
            flag2 = False

if not flag2:
    print('-1')
else:
    m = max(X_D)
    print(str(m))
    for i in range(m-1):
        print('1',end=' ')
    print('1')

    for i in range(N):
        ans = ''
        for x in range(abs(X[i][0])):
            if X[i][0]>=0:
                ans = ans + 'R'
            else:
                ans = ans + 'L'
        for y in range(abs(X[i][1])):
            if X[i][1]>=0:
                ans = ans+ 'U'
            else:
                ans = ans + 'D'

        flag3 = True
        for aaa in range(m - X_D[i]):
            if flag3:
                ans = ans + 'U'
                flag3 = False
            else:
                ans = ans + 'D'
                flag3 = True
        print(ans)

### FIXED CODE ###

N = int(input())
XY = [list(map(int, input().split(" "))) for _ in range(N)]
parity = (XY[0][0] + XY[0][1]) % 2
maxXY = 0
for x, y in XY:
    if (x + y) % 2 != parity:
        print("-1")
        exit()
    maxXY = max(x+y, maxXY)
arm = [1, 1, ]
if parity == 1:
    arm[1] = 2

tmp = arm[1]
m = 2

for _ in range(40):
    tmp *= 2
    m += 1
    arm.append(tmp)
    if tmp > maxXY:
        break
print(m)
print(" ".join(map(str, arm)))
armR = arm[::-1]
for x, y in XY:
    nowX, nowY = [x, y]
    ansR = ""
    for l in armR:
        if abs(nowX) >= abs(nowY):
            if nowX >= 0:
                nowX -= l
                ansR += "R"
            else:
                nowX += l
                ansR += "L"
        else:
            if nowY >= 0:
                nowY -= l
                ansR += "U"
            else:
                nowY += l
                ansR += "D"
    print(ansR[::-1])
### BUGGY CODE ###

def e_flatten_prime_factorization(MOD=10**9 + 7):
    N = int(input())
    A = [int(i) for i in input().split()]

    def prime_factorization_dict(n):
        from collections import defaultdict
        """nを素因数分解したときの素数とその指数の辞書"""
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table

    def prime_table(n):
        """n以下の素数のリスト(エラトステネスの篩)"""
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False  # 0と1は素数でない
        for j in range(2, int(n**0.5) + 1):
            if not is_prime[j]:
                continue
            for k in range(j * 2, n + 1, j):
                is_prime[k] = False  # jの倍数は素数でない
        return {i: 0 for i in range(n + 1) if is_prime[i]}

    lcm_prime = prime_table(10**6)
    for a in A:
        for base, exp in prime_factorization_dict(a).items():
            lcm_prime[base] = max(lcm_prime[base], exp)
    lcm = 1
    for base, exp in lcm_prime.items():
        lcm *= pow(base, exp, MOD)
        lcm %= MOD
    coefficient = sum(pow(a, MOD - 2, MOD) for a in A)
    return (lcm * coefficient) % MOD

print(e_flatten_prime_factorization())


### FIXED CODE ###

def e_flatten(MOD=10**9 + 7):
    from fractions import gcd
    from functools import reduce
    N = int(input())
    A = [int(i) for i in input().split()]

    def lcm(a, b):
        return a * b // gcd(a, b)

    def inv(n, mod=MOD):
        return pow(n, mod - 2, mod)

    l = reduce(lcm, A) % MOD
    ans = [(l * inv(a)) % MOD for a in A]
    return sum(ans) % MOD

print(e_flatten())
### BUGGY CODE ###

import numpy as np
from sklearn.utils.extmath import cartesian
 
k = int(input())
ls = [i for i in range(1, k+1)]
arr = cartesian([ls,ls,ls])
 
temp = np.gcd(arr[:, 0], arr[:, 1])
temp = np.gcd(temp, arr[:, 2])
print(sum(temp))

### FIXED CODE ###

import numpy as np
from sklearn.utils.extmath import cartesian

k = int(input())
ls = [i for i in range(1, k+1)]
arr = cartesian([ls,ls,ls])

print(np.gcd(np.gcd(arr[:, 0], arr[:, 1]), arr[:, 2]).sum())
### BUGGY CODE ###

import itertools
import numpy as np

n, m, q = list(map(int, input().split()))

a=[]
b=[]
c=[]
d=[]

for i in range(q):
    ai, bi, ci, di = list(map(int, input().split()))
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

def score(A, a, b, c, d):
    s = 0
    for i in range(len(a)):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            s += d[i]
    return s

h = 0
it = itertools.combinations_with_replacement(range(1, m+1), n)
A_list = np.array(list(it))


for A in A_list:
    h = max(h, score(A,a,b,c,d))

print(h)
 



### FIXED CODE ###

import itertools

n, m, q = list(map(int, input().split()))

a=[]
b=[]
c=[]
d=[]

for i in range(q):
    x = list(map(int, input().split()))
    a.append(x[0])
    b.append(x[1])
    c.append(x[2])
    d.append(x[3])

h = []
A_list = list(itertools.combinations_with_replacement(range(1, m+1), n))


for A in A_list:
    s = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            s += d[i]
    h.append(s)

print(max(h))
### BUGGY CODE ###

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

if 1 in a:
    while i<len(a):
        if a[i]!=i+1:
            del a[i]
            ans+=1
        else:
            i+=1
else:
    ans=-1
print(ans)


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
i=0
j=0
ans=0
if 1 in a:
    while j<N:
        if a[j]!=i+1:
            ans+=1
        else:
            i+=1
        j+=1
else:
    ans=-1
print(ans)
### BUGGY CODE ###

a, b, x = map(int, input().split())
ans = len([_ for _ in range(a, b+1) if _ % x ==0])

print(ans)

### FIXED CODE ###

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

#aの商と余り、bの商を求める
qa = a // x
qb = b // x
ra = a % x
#bの商からaの商を引く
ans = qb - qa

#ここまでの操作で、a以外の値の内、xで割り切れる値の数がansに入っているため、
#aが割り切れるかどうかで条件分岐させる
if ra == 0:
  print(ans+1)
else:
  print(ans)
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
while len(h)>1:
  if max(h[:-1])-1>h[-1]:
    print('No')
    exit()
  else:
    del h[-1]
print('Yes')

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
for i in range(n-1):
  if h[n-2-i]-1>h[n-1-i]:
      print('No')
      exit()
  elif h[n-2-i]-1==h[n-1-i]:
      h[n-2-i]=h[n-2-i]-1
print('Yes')
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())
mod = 10 ** 9 + 7

dp = [[0] * (r2 + 1) for _ in range(c2 + 1)]
for i in range(c2 + 1):
    dp[i][0] = 1
for i in range(r2 + 1):
    dp[0][i] = 1

for i in range(c2):
    for j in range(r2):
        dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]

ans = 0
for i in range(c1, c2 + 1):
    for j in range(r1, r2 + 1):
        ans += dp[i][j]
print(ans % mod)

### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())
mod = 10 ** 9 + 7

# dp = [[0] * (r2 + 1) for _ in range(c2 + 1)]
# for i in range(c2 + 1):
#     dp[i][0] = 1
# for i in range(r2 + 1):
#     dp[0][i] = 1

# for i in range(c2):
#     for j in range(r2):
#         dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]

# ans = 0
# for i in range(c1, c2 + 1):
#     for j in range(r1, r2 + 1):
#         ans += dp[i][j]
# print(ans % mod)
# brute forceであり、TLEする。


MAX = 10 ** 6 * 2 + 5
def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n,r):
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod 

def myfunc(r, c):
    return nCr(r + c + 2, r + 1) - 1


ans = myfunc(r2, c2)
ans -= myfunc(r2, c1 - 1)
ans -= myfunc(r1 - 1, c2)
ans += myfunc(r1 - 1, c1 - 1)
print(ans % mod)

# The result is the same as the below, but much faster.
# def nCr(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
### BUGGY CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_b
import sys
inf = sys.maxsize

n, k = map(int,input().split())
h = [int(i) for i in input().split()]

dp = [0 for _ in range(n)]
dp[0] = 0

for i in range(1, n): #段数
    tmp = min(k, i)
    dp[i] = min([dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, tmp + 1)])
    '''
    tmp = inf
    for j in range(1, k + 1): #一度に登る段数
        if i - j >= 0:
            tmp = min(tmp, dp[i - j] + abs(h[i] - h[i - j]))
    dp[i] = tmp
    '''

print(dp[n - 1])

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_b
import sys
inf = sys.maxsize

n, k = map(int,input().split())
h = [int(i) for i in input().split()]

dp = [0 for _ in range(n)]
dp[0] = 0

for i in range(1, n): #段数
    tmp = min(k, i)
    dp[i] = min([dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, tmp + 1)])
    '''
    tmp = inf
    for j in range(1, k + 1): #一度に登る段数
        if i - j >= 0:
            tmp = min(tmp, dp[i - j] + abs(h[i] - h[i - j]))
    dp[i] = tmp
    '''

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

N, M = map(int, input().split())
A = [int(i) for i in input().split()]

modDict = {}
B = 0
for i in range(N):
    B += A[i]
    if B%M in modDict:
        modDict[B%M] = modDict[B%M] + [i]
    else:
        modDict[B%M] = [i]

count = 0
for i in modDict:
    count += (len(modDict[i]) * (len(modDict[i]) -1))//2
    if i == 0:
        count += len(modDict[i])
print(count)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]

modDict = {}
B = 0
for i in range(N):
    B += A[i]
    if B%M in modDict:
        modDict[B%M] = modDict[B%M] + 1
    else:
        modDict[B%M] = 1

count = (modDict[0] if 0 in modDict else 0)
for i in modDict:
    count += (modDict[i] * (modDict[i] -1))//2
print(count)
### BUGGY CODE ###


import numpy as np
import copy
# N,K = map(int,input().split())
# V = list(map(int,input().split()))
N = 17
K = 100
V = [i for i in range(N)]

V = [0 for i in range(N)] + V + [0 for i in range(N)] 

dp = {}

# discardフラグを立てて，一度捨てると取れないように．
def search(start, end, k, own, discard=False):
    if k==K:
        return sum(own)
    key = tuple(own)
    if key in dp:
        return dp[key]
    val_Default = sum(own)
    val_A,val_B = 0,0
    if end-start >= 0 and not discard:
        val_A = search(start+1, end, k+1, own + [V[start]])
        val_B = search(start, end-1, k+1, own + [V[end]])
    if len(own) == 0 and discard:
        return val_Default
    val_Cs = []
    val_Ds = []
    for i,o in enumerate(own):
        own_new = copy.copy(own)
        own_new.pop(i)
        val_Cs.append(search(-1, -1, k+1, own_new, discard=True) )
        # val_Cs.append(search(start-1, end, k+1, own_new, discard=True) )
        # val_Ds.append(search(start, end+1, k+1, own_new, discard=True) )
    # print([val_Default, val_A, val_B], val_Cs , val_Ds)
    # dp[key] = max([val_Default, val_A, val_B] + val_Cs + val_Ds)
    dp[key] = max([val_Default, val_A, val_B] + val_Cs)
    # print(own, [val_Default, val_A, val_B], val_Cs, val_Ds)
    return dp[key]

r = search(N, 2*N-1, 0, [])
print(r)



### FIXED CODE ###

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

sumval = 0
for l in range(min(K+1,N+1)):
    for r in range(min(K+1-l,N-l+1)):
        sV = sorted(V[:l]+ V[N-r:])
        # i_div = 0
        # for i_div in range(len(sV)):
        #     if sV[i_div] > 0:
        #         break
        # for sute in range(min(K-r-l+1,len(sV),i_div+1)):
        for sute in range(min(K-r-l+1,len(sV))):
            c = sum(sV[sute:])
            sumval = max(c,sumval)

print(sumval)
### BUGGY CODE ###

import re
_, k = map(int, input().split())
S = input()
T = []
while S:
    if S[0] == "0":
        T += [re.match("0+", S).group()]
        S = S.lstrip("0")
    else:
        T += [re.match("1+", S).group()]
        S = S.lstrip("1")
T = [""]*("0" in T[0])+T+[""]*("0" in T[-1])
*L, = map(len, T)
A = [sum(L[:2*k+1])]
for i in range(len(T)-2*k-1):
    A += A[-1]-L[i]+L[i+2*k+1],
print(max(A[::2]))

### FIXED CODE ###

n, k = map(int, input().split())
S = input().replace("01", "0 1").replace("10", "1 0").split()
S = [""]*("0" in S[0])+S+[""]*("0" in S[-1])
*L, = map(len, S)
A = [sum(L[:2*k+1])]
for i in range(0, len(S)-2*k-1, 2):
    A += A[-1]-L[i]-L[i+1]+L[i+2*k+1]+L[i+2*k+2],
print(max(A))
### BUGGY CODE ###

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

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

res = 1
thr = 10**18
for a in A:
    res *= a

if res > thr:
    res = -1

print(res)


### FIXED CODE ###

# coding: utf-8

#import numpy as np

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

thr = 10**18

res = 1

if 0 in A:
    res = 0
else:
    for a in A:

        res *= a

        if res > thr:
            res = -1
            break

print(int(res))
### BUGGY CODE ###

def woo(x, y):
    res = [0 for i in range(0, x)]
    z = list(map(int, input().split()))
    for i in range(1, x):
        res[i] = min(abs(z[i] - z[j]) + res[j] for j in range(max(0, i - y), i))
    return res

if __name__ == '__main__':
    x, y = map(int, input().split())
    r = woo(x, y)
    f = len(r)-1
    print(r[f])



### FIXED CODE ###

from sys import stdin
n, k = [int(i) for i in stdin.readline().split(' ')]
h = [int(i) for i in stdin.readline().split(' ')]

minCosts = [0, abs(h[1]-h[0])]
for i in range(2, len(h)):
    minCosts.append(min([abs(h[i]-h[i-j])+minCosts[i-j] for j in range(1, min(i, k)+1)]))

print(minCosts[-1])