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

import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
# import math
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]





# @lru_cache(None)


r,g,b,n=l()
ans=0
r,g,b=sorted([r,g,b])
for i in range(n//r+1):
    for j in range(n//g+1):
        k=n-i*r-j*g
        if(k>=0 and k%b==0):
            ans+=1
print(ans)

### FIXED CODE ###


r,g,b,n=map(int,input().split())
ans=0
r,g,b=sorted([r,g,b])[::-1]
for i in range(n//r+1):
    for j in range(n//g+1):
        k=n-i*r-j*g
        if(k<0):
            break
        if(k>=0 and k%b==0):
            ans+=1
print(ans)
### BUGGY CODE ###

def resolve():
    N, K = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    tmp = -1
    for i in range(N - K + 1):
        sA = 1
        for j in range(K):
            sA *= A[i + j]
        if tmp > 0:
            if tmp < sA:
                print("Yes")
            else:
                print("No")
        tmp = sA


resolve()


### FIXED CODE ###

def resolve():
    from collections import deque
    N, K = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    for i in range(K, N):
        if A[i - K] < A[i]:
            print("Yes")
        else:
            print("No")


resolve()
### BUGGY CODE ###

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

def swap(a, b):
        return (b, a)

def modinv(a, m):
        b = m
        u = 1
        v = 0
        while b:
                t = a // b
                a -= t * b
                a, b = swap(a, b)
                u -= t * v
                u, v = swap(u, v)
        u %= m
        if u < 0:
                u += m
        return u

inv_factorial = [1]
prod = 1
for i in range(1, p):
    prod *= i
    prod %= p
    inv_factorial.append(modinv(prod, p))


# p-1C0, p-1C1, ..., p-1Cp-1
binomial = []
for i in range(p):
    l = i
    r = p-1-i
    binomial.append(prod * inv_factorial[l] * inv_factorial[r] % p)
    
ret = [0] * p
for i in range(p):
    if A[i] == 0:
        continue

    ret[0] += 1
    for j in range(p):
        ret[j] -= binomial[j] * (-i) ** (p-1-j)
        ret[j] %= p

ans = ''
for i in range(p):
    ans += str(ret[i]%p) + ' '

print(ans)
        


### FIXED CODE ###

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

def modinv(a, m):
        b = m
        u = 1
        v = 0
        while b:
                t = a // b
                a -= t * b
                a, b = b, a
                u -= t * v
                u, v = v, u
        u %= m
        if u < 0:
                u += m
        return u
        
inv_factorial = [1]
prod = 1
for i in range(1, p):
    prod *= i
    prod %= p
    inv_factorial.append(modinv(prod, p))

#p-1C0, p-1C1, ..., p-1Cp-1
comb = []
for i in range(p):
    l = i
    r = p-1-i
    comb.append(-1 * inv_factorial[l] * inv_factorial[r] % p)

ret = [0] * p
for i in range(p):
    if A[i] == 0:
        continue

    ret[0] += 1
    temp = 1
    for j in range(p):
        ind = p-j-1
        if j > 0:
            temp *= (-i)
            temp %= p
        ret[ind] -= comb[ind] * temp
        ret[ind] %= p

print(*ret)
### BUGGY CODE ###

#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,s):
  dx,dy = dire[di]
  if 0 <= x+dx < h and 0 <= y+dy < w:
    if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s:
      now.append((s,x+dx,y+dy,di))
      seen[x+dx][y+dy][di] = s
def turn(x,y,di,s):
  dx,dy = dire[di]
  if seen[x][y][di] > s:
    nex.append((s,x,y,di))
    seen[x][y][di] = s

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex[:]
  nex = []
  for i in range(k):
    last = now[:]
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        exit()
      add(x,y,di,s+1-int(bool(i)))
      for d in range(4):
        if di != d:
          turn(x,y,d,s)
  for xx in now:
    nex.append(xx)
print(-1)

### FIXED CODE ###

#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)
### BUGGY CODE ###

s,k = input().split()
K = int(k)
if s[-1] == "1":
  s += "0"
n = len(s)
ls = []
cnt = 0
for i in range(n):
  if s[i] == "0":
    ls.append(cnt)
    cnt = 0
  else:
    cnt += 1
l = len(ls)
sm = sum(ls)
mod = 998244353
dp = [[[0 for i in range(sm+1)] for j in range(sm+1)] for k in range(l+1)]
dp[0][0][0] = 1
smprv = 0
for i in range(1,l+1):
  num = ls[i-1]
  for j in range(smprv+num,sm+1):
    if j == smprv+num:
      dp[i][j][0] = 1
    for k in range(1,j+1):
      for m in range(j+1):
        if num >= m:
          dp[i][j][k] += dp[i-1][j-m][k]
        else:
          dp[i][j][k] += dp[i-1][j-m][k-(m-num)]
      dp[i][j][k] %= mod
  smprv += num
ans = 0
for i in range(sm+1):
  if i <= K:
    ans += dp[-1][-1][i]
    ans %= mod
print(ans)

### FIXED CODE ###

s,k = input().split()
K = int(k)
if s[-1] == "1":
  s += "0"
n = len(s)
ls = []
cnt = 0
for i in range(n):
  if s[i] == "0":
    ls.append(cnt)
    cnt = 0
  else:
    cnt += 1
l = len(ls)
sm = sum(ls)
mod = 998244353
dp = [[[0 for i in range(sm+1)] for j in range(sm+1)] for k in range(l+1)]
dp[0][0][0] = 1
smprv = 0
for i in range(1,l+1):
  num = ls[i-1]
  for j in range(smprv+num,sm+1):
    if j == smprv+num:
      dp[i][j][0] = 1
    for k in range(1,j+1):
      x = 0
      for m in range(j+1):
        if num >= m:
          x += dp[i-1][j-m][k]
        else:
          x += dp[i-1][j-m][k-(m-num)]
      dp[i][j][k] = x%mod
  smprv += num
ans = 0
for i in range(sm+1):
  if i <= K:
    ans += dp[-1][-1][i]
    ans %= mod
print(ans)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc174/tasks/abc174_c
K= int(input(" "))

if K%2==0 or K%5==0:
    print(-1)
elif K==1 or K==7:
    print(1)
else:
    B = 7
    i = 1
    while 1:
        if B%K==0:
            print(i)
            break
        else:
            B = 10 * B + 7
            i = i + 1

### FIXED CODE ###

#https://atcoder.jp/contests/abc174/tasks/abc174_c
K= int(input())

if K%2==0 or K%5==0:
    print(-1)
elif K==1 or K==7:
    print(1)
else:
    B = 7
    i = 1
    while 1:
        if B==0:
            print(i)
            break
        else:
            B = (10 * B + 7) % K
            i = i + 1
### BUGGY CODE ###

h, w = map(int, input().split())
lis = []
s = [str(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            lis.append([i, j])
ans = 0
for i in range(h):
    for j in range(w):
        num = 10 ** 7
        for x, y in lis:
            num = min(num, abs(i - x) + abs(j - y))
        ans = max(ans, num)
print(ans)


### FIXED CODE ###

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]

  black = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])

  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not M[bi - 1][bj]:
        M[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not M[bi][bj - 1]:
        M[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not M[bi + 1][bj]:
        M[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not M[bi][bj + 1]:
        M[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

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

C = []
for i in range(N):
    C.append(sum(A[i:]))
    
ans = len(list(filter(lambda x:x==0,C)))

for j in range(0,N)[::-1]:
    C = list(map(lambda x:x-A[j],C))[:j]
    ans += len(list(filter(lambda x:x==0,C)))
    
print(ans)

### FIXED CODE ###

from collections import defaultdict

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

C = defaultdict(int)

ans = 0
sumA = 0
for a in A:
    sumA += a
    C[sumA] += 1
    if C[sumA] >=2:
        ans += C[sumA]-1
        
for i in range(1,C[0]+1): ans+= 1
    
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()

r=s.count('R')
g=s.count('G')
b=s.count('B')

ng=0

all=r*g*b

#NGパターン数の洗い出し
for i in range(0,n-2):
  for j in range(i,n-1):
    if s[i]==s[j]:
      continue
    else:
      if j*2-i<=n-1:
#        print(i,j,j*2-i)
        if s[j]!=s[j*2-i] and s[j*2-i]!=s[i]:
          ng+=1
print(all-ng)

### FIXED CODE ###

n=int(input())
s=input()

#r=s.count('R')
#g=s.count('G')
#b=s.count('B')

r,g,b=0,0,0

for i in range(0,n):
  if s[i]=='R':
    r+=1
  elif s[i]=='G':
    g+=1
  else:
    b+=1

ng=0

all=r*g*b

#NGパターン数の洗い出し
for i in range(0,n-2):
  for j in range(i,n-1):
    if s[i]==s[j]:
      continue
    else:
      if j*2-i<=n-1:
#        print(i,j,j*2-i)
        if s[j]!=s[j*2-i] and s[j*2-i]!=s[i]:
          ng+=1
print(all-ng)
### BUGGY CODE ###

N = int(input())
n = N - 1
sum = 0
for i in range(n):
    sum = sum + i+1
print(sum)

### FIXED CODE ###

N = int(input())
print((N*(N-1))//2)
### BUGGY CODE ###

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

mx = 0
for i in range(N-K+1):
    mx = sum(P[i:i+K]) if sum(P[i:i+K])>mx else mx

print((mx+K)/2.)


### FIXED CODE ###

N,K = map(int, input().split())
P = list(map(int, input().split()))
S=0
for i in range(K):
    S += (P[i]+1)/2.
ans = S
for i in range(N-K):
    S += (P[i+K]-P[i])/2.
    ans = S if S > ans else ans 

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

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

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

ans = 1
for i in range(N):
    ans = ans*A[i]

if ans<=10**18:
    print("{}".format(ans))

else:
    print("{}".format(-1))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

N = int(input())
A = list(map(int, input().split()))
#A = np.array(A)
ans = 1
c = 1
for i in range(N):
    ans = ans*A[i]
    if ans > 10**18:
        #print("{}".format(-1))
        c=0
        break

if c==1:
    print("{}".format(ans))
elif c==0:
    if 0 in A:
        print("{}".format(0))
    else:
        print("{}".format(-1))
### BUGGY CODE ###

l,r=map(int,input().split())
a=0
b=2019
for i in range(l,r+1):
    for j in range(i+1,r+1):
        a=i*j%2019
        if b>a:
           b=a
print(b)

### FIXED CODE ###

l,r=map(int,input().split())
a=0
b=2019
if r-l>=2018:
   b=0
else:
   for i in range(l,r+1):
        for j in range(i+1,r+1):
            a=i*j%2019
            if b>a:
               b=a
print(b)
### BUGGY CODE ###

n = int(input())
for N in range(1, n+1):
    c = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                if i**2 + j**2 + k**2 + i*j + j*k + k*i == N:
                    c += 1
    print(c)
                

### FIXED CODE ###

n = int(input())
c = [0]*n
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            N = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if n >= N:
                c[N-1] += 1
for i in c:
    print(i)
### BUGGY CODE ###

s = input()
s = s[::-1]
li = ['maerd', 'remaerd', 'esare', 'resare']
t = ''

for i in range(len(s)):
  t = t + s[i]
  for c in li:
    if t == c:
      t = ''

if t == '':
  print('YES')
else:
  print('NO')

### FIXED CODE ###

s = input()
s = s[::-1]
li = ['maerd', 'remaerd', 'esare', 'resare']
t = ''

for i in range(len(s)):
  t = t + s[i]
  for c in li:
    if t == c:
      t = ''

if t == '':
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import product

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

Z1 = list(product([0,1],repeat=N//2))
Z2 = list(product([0,1],repeat=N-N//2))

d1 = defaultdict(lambda:5000)
d2 = defaultdict(lambda:5000)

for z in Z1:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[i]
            val_b += b[i]
            cost += c[i]
    if cost < d1[(val_a,val_b)]:
        d1[(val_a,val_b)] = cost

for z in Z2:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[N//2+i]
            val_b += b[N//2+i]
            cost += c[N//2+i]
    if cost < d2[(val_a,val_b)]:
        d2[(val_a,val_b)] = cost

vals = []
now = 1
while True:
    if Ma*now <= sum(a) and Mb*now <= sum(b):
        vals.append((Ma*now,Mb*now))
        now += 1
    else:
        break

ans = 5000
for k in d1.keys():
    for v in vals[::-1]:
        left_a = v[0]-k[0]
        left_b = v[1]-k[1]
        if left_a < 0 or left_b < 0:
            break
        if d1[k]+d2[(left_a,left_b)] < ans:
            ans = d1[k]+d2[(left_a,left_b)]

if ans == 5000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

amax = sum(a)
bmax = sum(b)

# dp[i][j][k]: 薬品iまで見て，Aがjグラム，Bがkグラムの最小予算
dp = [[[5000]*(bmax+1) for _ in range(amax+1)] for _ in range(N)]
dp[0][a[0]][b[0]] = c[0]
dp[0][0][0] = 0
for i in range(1,N):
    for j in range(amax+1):
        for k in range(bmax+1):
            if j == k == 0:
                dp[i][j][k] = 0
            elif j-a[i] < 0 or k-b[i] < 0:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-a[i]][k-b[i]]+c[i])

ans = 5000
now = 1
while True:
    if Ma*now <= amax and Mb*now <= bmax:
        if dp[N-1][Ma*now][Mb*now] < ans:
            ans = dp[N-1][Ma*now][Mb*now]
        now += 1
    else:
        break

if ans == 5000:
    print('-1')
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
Need = [[True]*N for _ in range(N)]
ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k] + A[k][j]
            if A[i][j] > Aikj:
                ans = -1
            if A[i][j] == Aikj:
                Need[i][j] = False

if ans != -1:
    for i in range(N):
        for j in range(i+1,N):
            if Need[i][j]:
                ans += A[i][j]
print(ans)

### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()
### BUGGY CODE ###

n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[100000 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]

queue = deque([])
now = [0,0]
b[0][0] = 1
while now != [n-1, m-1]:
    for i in range(4):
        if now[0] + y[i] < 0 or now[0] + y[i] >= n or now[1] + x[i] < 0 or now[1] + x[i] >= m:
            continue
        if a[now[0]+y[i]][now[1]+x[i]] == '.':
            queue.append([now[0]+y[i],now[1]+x[i]])
        b[now[0]+y[i]][now[1]+x[i]] = min(b[now[0]][now[1]] + 1, b[now[0]+y[i]][now[1]+x[i]])
    a[now[0]][now[1]] = "#"
    
    if queue == deque([]):
        print(-1)
        exit()
    now = queue.popleft()


ans = n * m - (b[n-1][m-1] + count)
print(ans)



### FIXED CODE ###

n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[-1 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]
queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()
    if now == [n-1,m-1]:
        print(n * m - (b[n-1][m-1] + count))
        exit()
    a[now[0]][now[1]] = "#"
    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m and b[now[0]+y[i]][now[1]+x[i]] == -1:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = b[now[0]][now[1]] + 1

print(-1)
### BUGGY CODE ###


#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	S = input()
	Q = int(input())
	cnt = 0
	s_start = ""
	s_end = ""
	for i in range(Q):
		q = list(input().split())
		if q[0] == "1":
			cnt += 1
		else:
			if q[1] == "1":
				if cnt % 2 == 0:
					s_start += q[2]
				else:
					s_end += q[2]
			else:
				if cnt % 2 == 0:
					s_end += q[2]
				else:
					s_start += q[2]

	if cnt % 2 == 0:
		ans = s_start[::-1] + S + s_end

	else:
		ans = s_end[::-1] + S[::-1] + s_start

	print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###


#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	S = input()
	Q = int(input())
	cnt = 0
	s_start = ""
	s_end = ""
	for i in range(Q):
		q = list(input().split())
		if q[0] == "1":
			cnt += 1
		else:
			if q[1] == "1":
				if cnt % 2 == 0:
					s_start += q[2]
				else:
					s_end += q[2]
			else:
				if cnt % 2 == 0:
					s_end += q[2]
				else:
					s_start += q[2]

	if cnt % 2 == 0:
		ans = s_start[::-1] + S + s_end

	else:
		ans = s_end[::-1] + S[::-1] + s_start

	print(ans)

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

import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = list(map(int,input().split()))
    AB.append([-b,a])
work = 0
for i in range(1,M+1):
    AB2 = list(filter(lambda x:x[1]<=i,AB))
    heapq.heapify(AB2)
    if not AB2:
        continue
    b,a = heapq.heappop(AB2)
    work += -b
    AB.remove([b,a])
print(work)

### FIXED CODE ###

import heapq
from collections import defaultdict
N,M = map(int,input().split())
AB = defaultdict(list)
for i in range(N):
    a,b = list(map(int,input().split()))
    if a not in AB:
        AB[a] = [-b]
    else:
        AB[a] += [-b]
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while len(check_que) != 0:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

n, k = map(int, input().strip().split())
hs = np.array(list(map(int, input().strip().split())))

dp = np.zeros(n, dtype=np.int)

for i in range(1, n):
    min_cost = 1e9
    costs = [
        dp[i - j] + abs(hs[i] - hs[i - j])
        for j in range(1, min(k + 1, i + 1))
    ]
    dp[i] = min(costs)

print(dp[n - 1])


### FIXED CODE ###

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

dp = [0] * n

for i in range(1, n):
    costs = []
    for j in range(1, k + 1):
        if i - j >= 0:
            cost = dp[i - j] + abs(hs[i] - hs[i - j])
            costs.append(cost)
    dp[i] = min(costs)

print(dp[n - 1])