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

n,k=map(int,input().split())
arr=list(map(int,input().split()))
temp=[0]*n
temp[n-2]=abs(arr[n-2]-arr[n-1])
if n>=3:
    i=n-3
    while i>=0:
        idx=i
        count=0
        min1=999999999999
        for j in range(idx+1,n):
            min1=min(min1,abs(arr[j]-arr[idx])+temp[j])
            count+=1
            if count==k:
                break
        temp[idx]=min1
        i-=1
print(temp[0])

### FIXED CODE ###

n,k=map(int,input().split())
arr=list(map(int,input().split()))
temp=[0]*n
temp[n-2]=abs(arr[n-2]-arr[n-1])
if n>=3:
    i=n-3
    while i>=0:
        idx=i
        count=0
        temp1=[]
        for j in range(idx+1,n):
            temp1.append(abs(arr[j]-arr[idx])+temp[j])
            count+=1
            if count==k:
                break
        temp[idx]=min(temp1)
        i-=1
print(temp[0])
### BUGGY CODE ###

def main():
    h, n = (int(x) for x in input().split())
    ab = []
    for _ in range(n):
        a, b = (int(x) for x in input().split())
        ab.append([a, b])
    dp = [float('inf')] * (h)
    for a, b in ab:
        for i in range(h):
            if i < a:
                dp[i] = min(dp[i], b)
            else:
                dp[i] = min(dp[i], dp[i - a] + b)
    print(dp[h - 1])
if __name__=='__main__':
    main()

### FIXED CODE ###

h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
max_a = max(a for a, _ in ab)
dp = [0] * (h + max_a)
for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in ab)
print(dp[h])
### BUGGY CODE ###

import itertools
n,k = map(int,input().split())
p = list(map(int,input().split()))
lstp = []
for i in range(n-k+1):
    lstp.append(0.5*(sum(p[i:i+k])+k))
print("{:.10f}".format(max(lstp)))

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
wa = sum(p[0:k])
next_wa = wa
for i in range(n-k):
    next_wa = next_wa - p[i] + p[i+k]
    if  next_wa > wa:
        wa = next_wa
print(0.5*(wa+k))
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[float('inf') for i in range(n)]
cost[0]=0
for i in range(n):
  for j in range(1,k+1):
    if i+j==n:
      break
    d=0
    if h[i]>h[j+i]:
      d=h[i]-h[i+j]
    else:
      d=h[i+j]-h[i]
    a=cost[i]+d
    if cost[i+j]>a:
      cost[i+j]=a
print(cost[-1])

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
h=np.array(list(map(int,input().split())),dtype=np.int64)
dp=np.full(n,10**10,dtype=np.int64)
dp[0]=0
for i in range(n-1):
  cost=np.abs(h[i]-h[i+1:i+k+1])
  np.minimum(dp[i+1:i+k+1],dp[i]+cost,out=dp[i+1:i+k+1])
print(dp[-1])
### BUGGY CODE ###

N = int(input())
bricks = list(map(int,input().split(" ")))
K=0
if 1 not in bricks:
    K = -1

else:
    K = 0
    value = 1
    while(value in bricks):
        index = bricks.index(value)
        bricks[value-1:index]=[]
        K += (index+1-value)
        value += 1

    K += len(bricks[value-1:])
print(K)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
count = 1
k = 0       #break time
 
for i in range(n):
    if a[i] == count:
        count += 1
    else:
        k += 1
 
if k == n:
    k = -1
 
print(k)
### BUGGY CODE ###

def f(a,b,N):
    tmpa,tmpb=[],[]
    for i in range(3):
        if a[i]<b[i]:
            tmpa.append(a[i])
            tmpb.append(b[i])
    a,b=tmpa,tmpb

    if len(a)==0: return N
    elif len(a)==1: return (N//a[0])*b[0]+N%a[0]

    memo=[i for i in range(N+1)]
    for i in range(1,N+1):
        tmp=[]
        for j in range(len(a)):
            if i-a[j]>=0: tmp.append(memo[i-a[j]]+b[j])
        if tmp!=[]: memo[i]=max(tmp)
    return memo[N]

import sys
N=int(input())

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

N=f(A,B,N)
N=f(B,A,N)
print(N)

### FIXED CODE ###

def f(a,b,N):

    tmpa,tmpb=[],[]
    for i in range(3):
        if a[i]<b[i]:
            tmpa.append(a[i])
            tmpb.append(b[i])
    a,b=tmpa,tmpb

    if len(a)==0: return N
    elif len(a)==1: return (N//a[0])*b[0]+N%a[0]

    elif len(a)==2:
        if a[0]<a[1]: a,b=a[::-1],b[::-1]

        i,ans=0,N
        while i*a[0]<=N:
            j=(N-i*a[0])//a[1]
            ans=max(ans,i*b[0]+j*b[1]+(N-i*a[0]-j*a[1]))
            i+=1
        return ans

    else:
        memo=[i for i in range(N+1)]

        for i in range(1,N+1):
            tmp=[]
            for j in range(len(a)):
                if i-a[j]>=0: tmp.append(memo[i-a[j]]+b[j])
            if tmp!=[]: memo[i]=max(tmp)
        return memo[N]

import sys
N=int(input())

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

N=f(A,B,N)
N=f(B,A,N)
print(N)
### BUGGY CODE ###

n = int(input())
ans = 0
S = [hash(''.join(sorted(input()))) for _ in range(n)]
T = set(S)
c = []

for i in T:
    c.append(S.count(i))
            
for j in c:
    ans += (j * (j-1) // 2)
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
S = {}
for _ in range(n):
    s = ''.join(sorted(input()))
    if s in S.keys():
        S[s] += 1
    else:
        S[s] = 1

for i in S.values():
    ans += (i*(i-1)) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
Flag = [0 for i in range(N)]
A = list(map(int,input().split()))
while len(A) != 1:
    A.sort()
    mi = min(A)
    for _ in range(1,len(A)):
        if A.count(1) > 1:
            del A[1:]
            break
        try:
            A[_] -= mi
            if A[_] <= 0:
                A.pop(_)
        except:
            pass
print(A[0])

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
while len(A) > 1:
    a_ = A[0]
    for x in range(1,len(A)):
        A[x] %= a_
    A = [ans for ans in A if ans > 0]
    A.sort()
print(A[0])
### BUGGY CODE ###

def swap(a, b):
    tmp = a
    a = b
    b = tmp

    return a, b

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

    dpList = [0] * N
    presentedDpList = [0] * N

    for i in range(N):
        dpList, presentedDpList = swap(dpList, presentedDpList)

        for j in range(i, N):
            if j == 0:
                dpList[j] = 0
            elif j == 1:
                dpList[j] = presentedDpList[j - 1] + abs(field[j] - field[j - 1])
            else:
                dpList[j] = min([presentedDpList[j - 1] + abs(field[j] - field[j - 1]), \
                                 presentedDpList[j - 2] + abs(field[j] - field[j - 2])])

    print(dpList[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

    dpList = [0] * N
    dpList[1] = abs(field[0] - field[1])

    for i in range(2, N):
        dpList[i] = min([dpList[i - 1] + abs(field[i] - field[i - 1]), dpList[i - 2] + abs(field[i] - field[i - 2])])
        
    print(dpList[-1])

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

def inputs(): return [int(x) for x in input().split()]
h,w = inputs()
meiro=[list(input()) for _ in range(h)]
visit = [[-1]*w for _ in range(h)]
#if meiro[0][0]=="#":
#  a = 1
#else:
#  a=0
stk = [[(0,0),(-1,-1),0]]
while stk:
    v,p,cnt = stk.pop()
    vx,vy = v
    px,py = p
    if w<=vx or h<=vy or (visit[vy][vx]!=-1 and visit[vy][vx]<cnt):
        continue
    if py==-1 and px==-1:
      if meiro[vy][vx]=="#":
        visit[vy][vx]=1
        cnt+=1
      else:
        visit[vy][vx]=0
    elif meiro[vy][vx]=="#"  and meiro[py][px]=="#":
        visit[vy][vx] = cnt
    elif meiro[vy][vx]=="#" and meiro[py][px]!="#":
        visit[vy][vx] = cnt+1
        cnt+=1
    elif meiro[vy][vx]==".":
        visit[vy][vx]=cnt
    dx = [0,1]
    dy = [1,0]
    for i in range(2):
        vx1 = vx+dx[i]
        vy1 = vy+dy[i]
        stk.append([(vx1,vy1),(vx,vy),cnt])
print(visit[h-1][w-1])

### FIXED CODE ###

def inputs(): return [int(x) for x in input().split()]
h,w = inputs()
meiro=[list(input()) for _ in range(h)]
visit = [[-1]*w for _ in range(h)]
if meiro[0][0]=="#":
    visit[0][0]=1
else:
    visit[0][0]=0
for j in range(1,w):
    if meiro[0][j]=="#":
        if meiro[0][j-1]=="#":
            visit[0][j]=visit[0][j-1]
        else:
            visit[0][j]=visit[0][j-1]+1
    if meiro[0][j]==".":
        visit[0][j]=visit[0][j-1]
for i in range(1,h):
    if meiro[i][0]=="#":
        if meiro[i-1][0]=="#":
            visit[i][0]=visit[i-1][0]
        else:
            visit[i][0]=visit[i-1][0]+1
    if meiro[i][0]==".":
        visit[i][0]=visit[i-1][0]
#print(visit)
for i in range(1,h):
    for j in range(1,w):
        if meiro[i][j]=="#":
            if meiro[i-1][j]=="#" and meiro[i][j-1]=="#":
                visit[i][j]=min(visit[i-1][j],visit[i][j-1])
            elif meiro[i-1][j]=="#":
                visit[i][j]=min(visit[i-1][j],visit[i][j-1]+1)
            elif meiro[i][j-1]=="#":
                visit[i][j]=min(visit[i-1][j]+1,visit[i][j-1])
            else:
                visit[i][j]=min(visit[i-1][j]+1,visit[i][j-1]+1)
        else:
            visit[i][j]=min(visit[i-1][j],visit[i][j-1])
print(visit[h-1][w-1])
### BUGGY CODE ###

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

opelates = []
for _ in range(q):
    opelates.append(list(map(int, input().split())))

for op in opelates:
    pre = op[0]
    nex = op[1]
    for i in range(n):
        if ali[i] == pre:
            ali[i] = nex
    print(sum(ali))

### FIXED CODE ###

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

opelates = []
for _ in range(q):
    opelates.append(list(map(int, input().split())))

numCntList = [0 for _ in range(10**5+1)]
for num in ali:
    numCntList[num] += 1
total = sum(ali)

for op in opelates:
    pre = op[0]
    nex = op[1]
    preCnt = numCntList[pre]
    if preCnt >= 1:
        numCntList[pre] = 0
        numCntList[nex] += preCnt
        total += (nex-pre)*preCnt
    print(total)
### BUGGY CODE ###

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

for i in a:
    ans *= i

if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
a.sort()
if a[0] == 0:
    ans = 0
    print(ans)
    exit()

for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()

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

from itertools import combinations

n = int(input())
l = list(map(int, input().split()))
cnt = 0
# print(list(combinations(l, 3)))
for ele in list(combinations(l, 3)):
    if ele[0] < ele[1] + ele[2] and ele[1] < ele[0] + ele[2] and ele[2] < ele[0] + ele[1]:
        cnt += 1

print(cnt)

### FIXED CODE ###

from itertools import combinations
import bisect
n = int(input())
l = list(map(int, input().split()))

l.sort()
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i-1, 0, -1):
        x = l[i] - l[j] + 1
        idx = bisect.bisect_left(l, x)
        if j > idx:
           cnt += j - idx
print(cnt)
### BUGGY CODE ###

from itertools import groupby
s = input()
n = len(s)
li = [0]
for i in range(n-1,-1,-1):
    p = s[i:]
    li.append(int(p)%2019)
li.sort()
lin = []
for key, value in groupby(li):
    lin.append(len(list(value)))
point = 0
for i in lin:
    point += i*(i-1)//2
print(point)

### FIXED CODE ###

from sys import stdin
s = stdin.readline().rstrip()
n = len(s)
dic = {}
dic[0] = 1
now = 0
mul = 1
for i in range(n-1,-1,-1):
    now = (now+(10*mul)*int(s[i]))%2019
    if now in dic:
        dic[now] += 1
    else:
        dic[now] = 1
    mul *= 10
    mul %= 2019
print(sum(dic[i]*(dic[i]-1)//2 for i in dic))
### BUGGY CODE ###

class charge:
    def __init__(self,x,y,z,v):
        self.coins = {10:x,50:y,100:z,500:v}
    def get_sum(self):
        return self.coins[10]*10 + self.coins[50]*50+self.coins[100]*100 + self.coins[500]*500
    def how_sheet(self):
        return self.coins[10] + self.coins[50] +self.coins[100] + self.coins[500]


def cal_charge(price,payment):
    a =[0,0,0,0]
    temp = payment - price
    if temp //500 !=0:
        a[3] = temp // 500
        temp = temp % 500
    if temp //100 !=0:
        a[2] = temp // 100
        temp = temp % 100
    if price //50 !=0:
        a[1] = temp // 50
        temp = temp % 50
    a[0] = temp //10
    return charge(*a)

if __name__ == "__main__":
    c =0
    while 1:
        price = int(input())
        if price ==0:break
        if c !=0:print("")
        max10,max50,max100,max500 = list(map(int,input().split(" ")))
        ans  = charge(max10,max50,max100,max500)
        minsh =  max10+max50+max100+max500
        i =0
        while i <= max500:
            j =0
            while  j <= max100:
                k =0
                while k <= max50:
                    l =0
                    while l <= max10:
                        payment = 500*i + 100*j +50*k + 10*l
                        if payment >= price:
                            temp = cal_charge(price,payment)
                            if minsh > temp.how_sheet():
                                minsh = temp.how_sheet()
                                ans = charge(l,k,j,i)
                        l +=1
                    k +=1
                j +=1
            i +=1
        for i in [10,50,100,500]:
            if ans.coins[i] !=0 :print("{} {}".format(i,ans.coins[i]))
        c +=1
    



### FIXED CODE ###

count = 0
coins =[10,50,100,500]
while 1:
    price = int(input())
    if price ==0:break
    if count !=0:print('')
    wallet= list(map(int,input().split(' ')))
    cash = wallet[0]* 10 + wallet[1] * 50 + wallet[2] * 100 + wallet[3] * 500
    charge = cash - price
    chargecoins = ((charge % 50) // 10,(charge % 100)//50,(charge % 500)//100,charge // 500)
    for  i in range(4):
        if wallet[i] > chargecoins[i]:print('{} {}'.format(coins[i],wallet[i]-chargecoins[i]))
    count +=1
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
from bisect import bisect, bisect_left


class Node:
    def __init__(self, idx):
        self.idx = idx
        self.v = 0
        self.parent = None
        self.children = []

    def add(self, x):
        self.v += x
        for c in self.children:
            c.add(x)

    def make_tree(self, addval=0):
        self.v += addval
        keyidx = bisect_left(brs_keys, self.idx)
        while keyidx < len(brs_keys) and brs_keys[keyidx] == self.idx:
            ni = brs[keyidx][1]
            node = nodes[ni]
            if not node.children:
                self.children.append(node)
            keyidx += 1
        for c in self.children:
            c.make_tree(self.v)

    def __str__(self):
        return str(self.idx)


N, Q = [int(_) for _ in input().split()]
nodes = [Node(i) for i in range(0, N)]

brs = []
for i in range(N - 1):
    a, b = [int(_) - 1 for _ in input().split()]
    brs.append((a, b))
    brs.append((b, a))

brs.sort()
brs_keys = [b[0] for b in brs]

# for n in nodes:
#     print(n.idx, [str(c) for c in n.children])

for i in range(Q):
    p, x = [int(_) for _ in input().split()]
    nodes[p - 1].v += x
    # nodes[p - 1].add(x)

nodes[0].make_tree()

print(*[n.v for n in nodes])

### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, Q = [int(_) for _ in input().split()]

edges = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = [int(_) for _ in input().split()]
    edges[a].append(b)
    edges[b].append(a)

P = [0] * (N + 1)

for q in range(Q):
    p, x = [int(_) for _ in input().split()]
    P[p] += x

que = deque()
que.append((1, 0))

while que:
    v, parent = que.popleft()
    P[v] += P[parent]
    for next_v in edges[v]:
        if next_v == parent: continue
        que.append((next_v, v))

# def f(v, parent=0):
#     P[v] += P[parent]
#
#     for next_v in edges[v]:
#         if next_v == parent: continue
#         f(next_v, v)
#
#
# f(1)
print(*[P[i] for i in range(1, N + 1)])
### BUGGY CODE ###

N = int(input())
A_array = list(map(int, input().split()))
ans = 0
check = [0 for _ in range(10 ** 6 + 5)]
A = A_array

for i in range(N):
  for j in range(int((len(check) - 1) / A[i])):
    check[A[i] * (j + 1)] += 1

for i in range(len(check) - 1):
  if i + 1 in A:
    if check[i + 1] == 1:
      ans += 1
    else:
      continue
  else:
    continue

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()                  #エラトステネスの篩にかけるためソート
Amax = A[-1]
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る。
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
    for q in range(Amax//p+1):
      dp[p*q] = 0         #A[i]の倍数をすべて0にする
    if A[i] != A[i+1]: 
      ans += 1            #A[i]が重複していなければカウント
if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
  ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l[i]+l[j] > l[k]: ans += 1
            else: break
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l = list(reversed(sorted(l)))
ans = 0
for i in range(1,n):
    start = 0
    for j in range(i+1,n):
        l2 = l[i]+l[j]
        for k in range(start, i):
            if l[k] < l2:
                start = k
                ans += i - k
                break
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def input(): return sys.stdin.readline()[:-1]


sys.setrecursionlimit(10**8)
INF = 1001001001001
n, m, l = map(int, input().split())
D = [[INF]*n for i in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    D[a-1][b-1] = c
    D[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            D[i][j] = min(D[i][j], D[i][k]+D[k][j])


for i in range(n):
    for j in range(n):
        D[i][j] = 1 if D[i][j] <= l else INF

for k in range(n):
    for i in range(n):
        for j in range(n):
            D[i][j] = min(D[i][j], D[i][k]+D[k][j])
# for i in D:
#     print(i)

q = int(input())
for i in range(q):
    s, g = map(int, input().split())
    s -= 1
    g -= 1
    print(D[s][g]-1 if D[s][g] != INF else -1)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, dijkstra
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

# f = floyd_warshall(G,directed=True(有向か、defaultはTrue))
# d = dijkstra(G, indices=0,directed=True(有向か、defaultはTrue))
n,m,l=map(int,input().split())
rinsetsu=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    rinsetsu[a-1][b-1]=c
    rinsetsu[b-1][a-1]=c

# G = csgraph_from_dense(rinsetsu, null_value=0)
f = floyd_warshall(rinsetsu,directed=True)
# print(f)
for i in range(n):
    for j in range(n):
        f[i][j]= 1 if 1<=f[i][j]<=l else 0
# print(f)
f2= floyd_warshall(f,directed=True)

q = int(input())
for i in range(q):
    s,g=map(int,input().split())
    s-=1;g-=1
    print(int(f2[s][g])-1 if f2[s][g]!=float("inf") else -1)

# print(f2)
### BUGGY CODE ###

import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [20]
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0).tolist()) # 列方向

    flag = True
    for r in rows:
        if np.any(np.array(r) > K):
            flag = False
            break
    if not flag:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if np.any(np.array(cnt) > K):
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

print(ans)

### FIXED CODE ###

from itertools import product
H, W, K = map(int, input().split())
G = [list(map(int, list(input()))) for _ in range(H)]

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [H]
    rows = []
    for i in range(len(div) - 1):
        row = []
        for j in range(W):
            tmp = 0
            for k in range(div[i], div[i + 1]):
                tmp += G[k][j]
            row.append(tmp)
        rows.append(row)
        
    flag = True
    for row in rows:
        if [r for r in row if r > K]:
            flag = False
            break
    if not flag:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if [c for c in cnt if c > K]:
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

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

INF=10**15
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[INF for i in range(N)]
dp[0]=0
for i in range(1,N):
    k=1
    while i-k>-1 and k<=K:
        dp[i]=min(dp[i],dp[i-k]+abs(h[i]-h[i-k]))
        k+=1
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
h=list(map(int,input().split()))
h=np.array(h)
cost=np.zeros(N+1)
cost[1]=0
cost[2]=abs(h[1]-h[0])
for i in range(3,N+1):
    x=1 if i-K<=1 else i-K
    cost[i]=(cost[x:i]+abs(h[i-1]-h[x-1:i-1])).min()
print(int(cost[N]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
*A, = map(int, input().split())
C = [0]*4
for a in A:
    C[a] += 1

c1, c2, c3 = C[1:]
memo = {}
memo[0, 0, 0] = 0.
def dfs(a, b, c):
    key = (a, b, c)
    if key in memo:
        return memo[key]
    r = 0
    if a:
        r += a*(dfs(a-1, b, c)+1)
    if b:
        r += b*(dfs(a+1, b-1, c)+1)
    if c:
        r += c*(dfs(a, b+1, c-1)+1)
    p = (a + b + c)
    memo[key] = r = (r + N - p) / p
    return r
print("%.10f" % dfs(c1, c2, c3))

### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())
C = [0]*4
for a in A:
    C[a] += 1

c1, c2, c3 = C[1:]
dp = [[[0]*(c1+c2+c3+1) for i in range(c2+c3+2)] for j in range(c3+2)]
for c in range(c3+1):
    M1 = c2+c3-c
    T = dp[c-1]
    S = dp[c]
    for b in range(M1+1):
        M2 = N-b-c
        X = S[b-1]; Y = S[b]
        Z = T[b+1]
        for a in range(M2==N, M2+1):
            r = N
            if a:
                r += a*Y[a-1]
            if b:
                r += b*X[a+1]
            if c:
                r += c*Z[a]
            Y[a] = r / (a+b+c)
print("%.10f" % dp[c3][c2][c1])
### BUGGY CODE ###

def edu_dp_f_lcs():
    s = input()
    t = input()
    dp = [[''] * (len(t)+1) for _ in range(len(s)+1)]
    for i in range(0, len(s)):
        for j in range(0, len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + s[i]
            elif len(dp[i+1][j]) > len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]
    print(dp[len(s)][len(t)])


edu_dp_f_lcs()

### FIXED CODE ###

def edu_dp_f_lcs():
    s = input()
    t = input()
    slen = len(s)
    tlen = len(t)
    dp = [[0] * (tlen+1) for _ in range(slen+1)]
    for i in range(slen):
        for j in range(tlen):
            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])

    l = dp[slen][tlen]
    i = slen-1
    j = tlen-1
    ans = ''
    while l > 0:
        if s[i] == t[j]:
            ans = s[i]+ans
            j -= 1
            i -= 1
            l -= 1
        elif dp[i+1][j+1] == dp[i][j+1]:
            i-=1
        else:
            j-=1
    print(ans)

edu_dp_f_lcs()