Harryxun/stf_run huggingface dataset:
s=input()
t=input()

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s="".join([ z for z in s if z in mnmz])
t="".join([ z for z in t if z in mnmz])
if len(s)>len(t): s, t = t, s

# init
dp=[0]*len(s)
res={}
#dp
for i in range(len(t)):
    #print(dp)
    prev=dp[0]
    if dp[0]==0 and t[i]==s[0]:
        dp[0]=1
        res[1]=[s[0]]
        collector={}
    for j in range(1, len(s)):
        temp = max(dp[j-1], dp[j])
        if s[j]==t[i]:
            if temp<prev+1:
                temp=prev+1
                if temp not in res: res[temp]=[]
                collector[temp]=res[prev]+[s[j]]
        prev, dp[j] = dp[j], temp
    res.update(collector)
    if dp[-1]==len(s): break

#print(dp)

print("".join(res[dp[-1]]))

### FIXED CODE ###

s=[ord(ch)-97 for ch in input()]
t=[ord(ch)-97 for ch in input()]

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame init
for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        if s[j]==t[i]:
            dp[i][j]=dp[i-1][j-1]+1
        else: dp[i][j]=(dp[i][j-1] if dp[i][j-1]>dp[i-1][j] else dp[i-1][j])

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>=0 and j>=0:
    if s[j]==t[i]: #and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if i==0 and j==0: break
    if j>0 and dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)


print("".join(chr(i+97) for i in reversed(res)))
n,k=map(int,input().split())
l=[]
for _ in range(n):
    l.append(int(input()))
l.sort()
a=0
for i in range(n-k+1):
    if i==0:
        a=l[i+k-1]-l[i]
    else:
        a=min(a,abs(l[i+k-1]-l[i]))
print(a)

### FIXED CODE ###

n=int(input())
l=[]
for _ in range(n):
    l.append(int(input()))
print(sum(l)-int(max(l)/2))
from collections import deque
n, m, k = [int(n) for n in input().split()]
A = deque([int(n) for n in input().split()])
B = deque([int(n) for n in input().split()])
dp = [0] * k

t, n = 0, 0
while True:
    a = A[0] if A else None
    b = B[0] if B else None
    if a and a < b:
        d = A.popleft()
    elif b:
        d = B.popleft()
    t += d
    if t > k:
        break
    n += 1
print(n)


### FIXED CODE ###

from numpy import cumsum
n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = cumsum([0] + A)
B = cumsum([0] + B)
n_read = 0
l = len(B) - 1
for i, a in enumerate(A):
    if a > k:
        break
    for j, b in enumerate(B[l::-1]):
        if a + b <= k:
            l -= j
            n_read = max(n_read, i + l)
            break
print(n_read)
s = int(input())
d = list(map,input().split())
sum = 0
 
for i in range(n):
  for j in range(i+1,n):
    sum += (d[i]*d[j])
print(ans)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
sum = 0
 
for i in range(n):
  for j in range(i+1,n):
    sum += (d[i]*d[j])
print(sum)
n=int(input())
l=[]
for i in range(n):
  l.append(reversed(list(map(int,input().split()))))
l=sorted(l)
for i in range(101):
  for j in range(101):
    b=True
    h=abs(i-l[-1][2])+abs(j-l[-1][1])+l[-1][0]
    for i in range(n-1):
      if max(h-abs(i-l[-2-i][2])-abs(j-l[-2-i][1]),0)!=l[-2-i][0]:
        b=False
    if b:
      print(i,j,h)
      break
      
    
           

### FIXED CODE ###

n=int(input())
l=[]
l1=[]
for i in range(n):
  l1=list(map(int,input().split()))
  l1=l1[::-1]
  l.append(l1)      
l=sorted(l)
for i in range(101):
  for j in range(101):
    b=True
    h=abs(i-l[-1][2])+abs(j-l[-1][1])+l[-1][0]
    for k in range(n-1):
      if max(h-abs(i-l[-2-k][2])-abs(j-l[-2-k][1]),0)!=l[-2-k][0]:
        b=False
    if b:
      print(i,j,h)
      break
H, W=map(int, input().split())
maxK=80*80+1
A=[list(map(int, input().split())) for _ in range(H)]
B=[list(map(int, input().split())) for _ in range(H)]
C=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
dp=[[[0 for _ in range(maxK+1)] for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][C[0][0]]=1
for i in range(1, H+1):
    for j in range(1, W+1):
        for k in range(maxK):
            if dp[i-1][j][k]==1 or dp[i][j-1][k]==1:
                k_candidate1, k_candidate2=abs(k-C[i-1][j-1]), abs(k+C[i-1][j-1])
                if k_candidate1<maxK:
                    dp[i][j][k_candidate1]=1
                if k_candidate2<maxK:
                    dp[i][j][k_candidate2]=1
for k in range(maxK):
    if dp[H][W][k]==1:
        print(k)
        break

### FIXED CODE ###

A=list(map(int, input().split()))
if sum(A)>=22:
    print('bust')
else:
    print('win')
w,h,n=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
a1=[];a2=[];a3=[];a4=[]
for i in a:
  if i[2]==1:a1.append(i[0])
  else:pass
for i in a:
  if i[2]==2:a2.append(i[0])
  else:pass
for i in a:
  if i[2]==3:a3.append(i[1])
  else:pass
for i in a:
  if i[2]==4:a4.append(i[1])
  else:pass
if max(a1)-min(a2)<0:x=max(a1)-min(a2)
else:x=0
if max(a3)-min(a4)<0:y=max(a3)-min(a4)
else:y=0
print(x*y)

### FIXED CODE ###

w,h,n=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
a1=[0];a2=[w];a3=[0];a4=[h]
for i in a:
  if i[2]==1:a1.append(i[0])
  else:pass
for i in a:
  if i[2]==2:a2.append(i[0])
  else:pass
for i in a:
  if i[2]==3:a3.append(i[1])
  else:pass
for i in a:
  if i[2]==4:a4.append(i[1])
  else:pass
if max(a1)-min(a2)<0:x=max(a1)-min(a2)
else:x=0
if max(a3)-min(a4)<0:y=max(a3)-min(a4)
else:y=0
print(x*y)
n,k=map(int,input())
ans=0
while n>0:
  ans+=1
  n=n//k
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
ans=0
while n>0:
  ans+=1
  n=n//k
print(ans)
n,x=map(int,input().split())
a=sort(list(map(int,input().split())))

s=0
num=0
for i in range(len(a)):
  if x>=a[i]:
    x-=a[i]
    num+=1
  else:
    break
    
print(num)

### FIXED CODE ###

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

s = 0
num = 0
if x>sum(a):
  print(len(a)-1)
else:
  for i in range(len(a)):
      if x >= a[i]:
          x -= a[i]
          num += 1
      else:
          break

  print(num)
n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
cnt=[0]*(10**5)
for i in range(n):
    cnt[a[i]]+=1
for i in range(n-1):
    tmp=cnt[a[i]]+cnt[a[i]+1]+cnt[a[i]+2]
    ans=max(tmp,ans)
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
cnt=[0]*(10**5+2)#a[i]+2
for i in range(n):
    cnt[a[i]]+=1
for i in range(n):
    tmp=cnt[a[i]]+cnt[a[i]+1]+cnt[a[i]+2]
    ans=max(tmp,ans)
print(ans)
if(input() / 500 < input())
	print("Yes")

### FIXED CODE ###

N = int(input())
A = int(input())
 
if(N % 500 <= A):
  print("Yes")
else:
  print("No")
import heapq


def heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap) - 1)


def heappop_max(heap):
    lastelt = heap.pop()
    if heap:
        return_item = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return return_item
    return lastelt


X, Y, Z, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)
ans = []
heap_queue = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            heappush_max(heap_queue, A[i] + B[j] + C[k])
for k in range(K):
    print(heappop_max(heap_queue))


### FIXED CODE ###

def main():
    X, Y, Z, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]

    AB = []
    ABappend = AB.append
    for i in range(X):
        for j in range(Y):
            ABappend(A[i] + B[j])
    AB.sort(reverse=True)
    ABC = []
    ABCappend = ABC.append
    for i in range(min(K, X*Y)):
        for j in range(Z):
            ABCappend(AB[i] + C[j])
    ABC.sort(reverse=True)
    print('\n'.join(map(str, ABC[:K])))


if __name__ == '__main__':
    main()
N,A,B = map(int,input().split())

print(min(N*A,B))

### FIXED CODE ###

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

print((A+B+1)//2)
n=int(input())
b=[input() for i in range(n)]
m=int(input())
r=[input() for i in range(m)]
ans=[0]
for i in set(b)
    ans.append(b.count(i)-r.count(i))
print(max(ans))

### FIXED CODE ###

import collections

n=int(input())
lb=[input() for i in range(n)]
m=int(input())
lr=[input() for i in range(m)]

for i in range(len(lr)):
    if lr[i] in lb:
        lb.remove(lr[i])
    else:
        pass
if lb==[]:
    ans=0
else:
    s=collections.Counter(lb)
    ans=s.most_common()[0][1]      

print(ans)
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

a = []
for i in range(N):
	A = INT()
	a.append([LIST() for _ in range(A)])

maxv = 0
for i in range(2**N):
	s = "{:0" + str(3) + "b}"
	F = [int(i) for i in s.format(i)]
	flag = 0
	for j in range(N):
		if F[j] == 1:
			for k in range(len(a[j])):
				if a[j][k][1] == 1:
				 	if F[a[j][k][0] - 1]*a[j][k][1] == 0:
				 		flag = 1
					 	break
				else:
					if F[a[j][k][0] - 1]*a[j][k][1] == 0:
						flag = 1
						break

	if flag == 1:
		continue

	wa = sum(F)
	if maxv < wa:
		maxv = wa

print(maxv)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

a = []
for i in range(N):
	A = INT()
	a.append([LIST() for _ in range(A)])

maxv = 0
for i in range(2**N):
	s = "{:0" + str(N) + "b}"
	F = [int(i) for i in s.format(i)]
	flag = 0
	for j in range(N):
		if F[j] == 1:
			for k in range(len(a[j])):
				if a[j][k][1] == 1:
				 	if F[a[j][k][0] - 1]*a[j][k][1] == 0:
				 		flag = 1
					 	break
				else:
					if F[a[j][k][0] - 1] == 0:
						continue
					if F[a[j][k][0] - 1]*a[j][k][1] == 0:
						flag = 1
						break

	if flag == 1:
		continue

	wa = sum(F)
	if maxv < wa:
		maxv = wa

print(maxv)
x = int(input())
y = list(map(int, input().split(" ")))

for i in range(x - 1):
  if y[i] < 0:
    y[i] *=-1
    y[i + 1] *=-1

if y[-1] < 0 and abs(min(y[0:-2])) < abs(y[-1]) :
  y[-1] *= -1
  y[y.index(min(y[0:-2]))] *= -1

print(sum(y))

### FIXED CODE ###

x = int(input())
y = list(map(int, input().split(" ")))

for i in range(x - 1):
  if y[i] < 0:
    y[i] *=-1
    y[i + 1] *=-1

if y[-1] < 0 and abs(min(y[0:-1])) < abs(y[-1]) :
  y[-1] *= -1
  y[y.index(min(y[0:-1]))] *= -1

print(sum(y))
n=map(int,raw_input().split())
a=n[0]
b=n[1]
print(a*b)
print(' ')
print((2*a)+(2*b))


### FIXED CODE ###

#cording; UTF-8
a,b=[int(x) for x in input().split()]

S = a*b
L = 2*(a+b)
print(S,L)
a = input()
b = input()
c = input()
 
def common(s1, s2):
	l1 = len(s1)
	l2 = len(s2)
	memo = [[0 for i in range(l1+2)] for j in range(l2+2)]
 
	for idx1,w1 in enumerate(s1):
		for idx2,w2 in enumerate(s2):
			if w1==w2 or w1=='?'or w2=='?':
				memo[idx2+1][idx1+1] = memo[idx2][idx1] + 1
 
	return memo
m1 = 0
m2 = 0
m3 = 0
for l in common(a,b):
	if max(l)>m1:
		m1 = max(l)
for l in common(a,c):
	if max(l)>m2:
		m2 = max(l)
for l in common(b,c):
	if max(l)>m3:
		m3 = max(l)
ans=len(a)+len(b)+len(c)-m1-m2-m3+min([m1,m2,m3])
 
print(ans)

### FIXED CODE ###

l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
]
N = int(input())
print(l[N-1])
if re.match(r'C.*F', s):
    print(YES)
else:
    print(NO)

### FIXED CODE ###

import re

s = input()

if re.match(r'.*C.*F', s):
    print('Yes')
else:
    print('No')
def num_of_perms(n, r):
    p = 1
    for i in range(int((n+1)/2)):
        if i < r and r < n - i:
            p *= (n - i)
    return p

[N, K] = map(int, input().split())
[a1, b1] = map(int, input().split())
Es = [a1, b1]
for _ in range(1, N-1):
    [a, b] = map(int, input().split())
    Es.append(a)
    Es.append(b)

res = K * (K-1)
res %= 1000000007
for i in range(0, N):
    j = i + 1
    c = Es.count(j)
    if c > K-1:
        res = 0
        break
    res *= num_of_perms((K-2), (c-1))
    res %= 1000000007

print(res)


### FIXED CODE ###

from itertools import groupby

[N, K] = map(int, input().split())

num_of_perms = [1] * (K-1)
for i in range(1, K-1):
    num_of_perms[i] = num_of_perms[i-1] * ((K - 2) - i + 1) % 1000000007

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

if N == 1:
    res = K
else:
    res = K * (K-1)
    res %= 1000000007
    for g in groupby(sorted(Es)):
        c = len(list(g[1]))
        if c > K-1:
            res = 0
            break
        res *= num_of_perms[c-1]
        res %= 1000000007

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

d = [1] * (N+1)
d[0] -= A[0]
for i in range(N):
    d[i+1] = d[i] * 2 - A[i+1]

if d[-1] < 0:
    print(-1)
    print(aaaaaaa)
    exit()
else:
    d[-1] = A[-1]
for i in range(N, 0, -1):
    x = d[i]
    x += A[i-1]
    if d[i-1] * 2 < x:
        y = x - A[i-1]
        if (y+1) // 2 + A[i-1] <= d[i-1] * 2:
            x = d[i-1] * 2
    if d[i-1]*2 < x:
        print(-1)
        print(aaaaaaa)
        exit()
    d[i-1] = min(x, d[i-1]+A[i-1])
print(d)
print(sum(d))


### FIXED CODE ###

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

d = [1] * (N+1)
d[0] -= A[0]
for i in range(N):
    d[i+1] = d[i] * 2 - A[i+1]

if d[-1] < 0:
    print(-1)
    exit()
else:
    d[-1] = A[-1]
for i in range(N, 0, -1):
    x = d[i]
    x += A[i-1]
    if d[i-1] * 2 < x:
        y = x - A[i-1]
        if (y+1) // 2 + A[i-1] <= d[i-1] * 2:
            x = d[i-1] * 2
    d[i-1] = min(x, d[i-1]+A[i-1])
print(sum(d))
S = input()
A = 0
for s in S:
	if s == "-":
		A--
	if s == "+":
		A++
print(A);

### FIXED CODE ###

S = input()
A = 0
for s in S:
	if s == "-":
		A -= 1
	if s == "+":
		A += 1
print(A);
def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    import sys
    input = sys.stdin.readline
    n, m, l = map(int, input().split())
    inf = 10 ** 20
    ar = [[inf] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        ar[a - 1][b - 1] = c
        ar[b - 1][a - 1] = c
    x = floyd_warshall(ar)
    br = [[inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i][j] = 1
                br[j][i] = 1
    y = floyd_warshall(br)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        p = y[s - 1, t - 1]
        print(int(p) - 1 if p < inf else -1)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    import sys
    input = sys.stdin.readline
    n, m, l = map(int, input().split())
    inf = 10 ** 20
    ar = np.zeros((n, n))
    for _ in range(m):
        a, b, c = map(int, input().split())
        ar[a - 1, b - 1] = c
        ar[b - 1, a - 1] = c
    x = floyd_warshall(ar)
    br = np.zeros((n, n))
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i, j] = 1
                br[j, i] = 1
    y = floyd_warshall(br)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        p = y[s - 1, t - 1]
        print(int(p) - 1 if p < inf else -1)


if __name__ == "__main__":
    resolve()
a, b = int(input().split())
if a // 2 == a / 2 or b // 2 == b / 2:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

a, b = map(int, input().split())
if a // 2 == a / 2 or b // 2 == b / 2:
  print('Even')
else:
  print('Odd')
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
A = sorted(A)
B = [0 for i in range(N)]
for i in range(N-1):
  B[i] = A[i + 1] - A[i]
B[N - 1] = N - A[N] + a[0]
ans = N - max(B)
print(ans)

### FIXED CODE ###

K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
A = sorted(A)
B = [0 for i in range(N)]
for i in range(N-1):
  B[i] = A[i + 1] - A[i]
B[N - 1] = K - A[N - 1] + A[0]
ans = K - max(B)
print(ans)
H,W = list(map(int, input().split(' ')
h,w = list(map(int, input().split(' ')
pritn((H-h)*(W-w))

### FIXED CODE ###

H,W = list(map(int, input().split(' ')))
h,w = list(map(int, input().split(' ')))
print((H-h)*(W-w))
from numba inmport 

@jit
def do():
  data = input().split()
  monsters = int(data[0])
  smash = int(data[1])
 
  mon_str = input().split()
  mon_str = [int(b) for b in mon_str]
  count = 0
 
  for i in range(smash):
      try:
          enemy = mon_str.index(max(mon_str))
          del mon_str[enemy]
    
      except ValueError:
          pass
  print(sum(mon_str))
 
do()

### FIXED CODE ###

data = input().split()
strengh = int(data[0])
attack = int(data[1])
count = 0

while strengh > 0:
    strengh -= attack
    count += 1

print(count)
import math
class Graph(object):
    def __init__(self,v):
        self.v = v
        self.visited = [False for i in range(v)]
        self.adj = [[] for i in range(v)]
        self.parent = [-1 for i in range(v)]
        self.distance = [0 for i in range(v)]

    def AddEdge(self,a,b):
        self.adj[a].append(b)
        self.adj[b].append(a)

    def BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)

    def CycleDetection_Using_BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)
                else:
                    if self.parent[cur]!=child:
                        return True

        return False

NK= list(map(int,input().split(' ')))
n,k = NK[0] , NK[1]
h = list(map(int,input().split(' ')))
dp = [0]*n
for i in reversed(range(n)):
    m=math.inf
    if i==n-1:
        dp[i] = 0
    else:
        for j in range(1,k+1):
            Move = i+j
            if Move<=n-1:
                m = min(m,dp[Move]+abs(h[i]-h[Move]))
        dp[i] = 0 if m==math.inf else m
print(dp[0])




### FIXED CODE ###

import math
from functools import lru_cache
def Frog1():
    n = int(input())
    h = list(map(int,input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        if i==n-2:
            return abs(h[i]-h[i+1])
        return min(Solve(i+1)+abs(h[i]-h[i+1]),Solve(i+2)+abs(h[i]-h[i+2]))
    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        elif i==n-2:
            dp[i] = abs(h[i]-h[i+1])
        else:
            dp[i] = min(dp[i+1]+abs(h[i]-h[i+1]),dp[i+2]+abs(h[i]-h[i+2]))
    print(dp[0])
def Frog2():
    n,k = input().split(' ')
    n,k = int(n),int(k)
    h = list(map(int, input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        ans = math.inf
        for j in range(1,k+1):
            new_i = i+j
            if new_i<=n-1:
                ans = min(ans , Solve(new_i)+abs(h[i]-h[new_i]))
            else:
                break
        return ans

    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        else:
            ans = math.inf
            for j in range(1,k+1):
                new_i = i+j
                if new_i<=n-1:
                    ans = min(ans,dp[new_i]+abs(h[i]-h[new_i]))
                else:
                    break
            dp[i] = ans
    print(dp[0])

Frog2()
S = input()
N = len(S)
center_i = N//2
center = S[center_i]

ans = N//2 + N%2
if N%2==0 and center != S[center_i+1]:
    print(ans)
    exit()
l = center_i - 1
r = center_i + 1 + (N%2==0)
while l >= 0:
    if not (S[l] == center == S[r]):
        break
    l -= 1
    r += 1
    ans += 1
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
center_i = N//2
center = S[center_i]

ans = N//2
l = r = center_i
if N%2==0:
    l -= 1
while l >= 0:
    if not (S[l] == center == S[r]):
        break
    l -= 1
    r += 1
    ans += 1
print(ans)
N, A, B = map(int, input().split())

count = 0

for i in range(1, N+1):
  tmp = sum(list(str(i)))
  if A <= tmp <= B:
    count += 1
    
print(count)

### FIXED CODE ###

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

count = 0

for i in range(1, N+1):
  str_i = str(i)
  tmp = 0
  for j in range(len(str_i)):
    tmp += int(str_i[j])
  if A <= tmp <= B:
    count += i
    
print(count)
X,Y = map(int,input().split())
ans = 0
while X <= Y:
	ans += 1
	X * = 2
print(ans)

### FIXED CODE ###

X,Y = map(int,input().split())
ans = 0
while X <= Y:
	ans += 1
	X *= 2
print(ans)
n = input()
print("Yes" if n[0]=n[1]=n[2]=n[3] or n[0]=n[1]=n[2] or n[1]=n[2]=n[3] else "No")

### FIXED CODE ###

n = input()
print("Yes" if n[0]==n[1]==n[2]==n[3] or n[0]==n[1]==n[2] or n[1]==n[2]==n[3] else "No")
def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

mod = 10 ** 9 + 7
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    quit()
n = (x + y) // 3
m = min(x, y) - n

fac, inv = factorial(n, mod)
print(fac[n] * inv[n-m] * inv[m] % mod) # nCm


### FIXED CODE ###

def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

mod = 10 ** 9 + 7
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    quit()
n = (x + y) // 3
if x < n or y < n:
    print(0)
    quit()

m = min(x, y) - n
fac, inv = factorial(n, mod)
print(fac[n] * inv[n-m] * inv[m] % mod) # nCm