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

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

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
#fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
#    fac_inv.append(inv(f))

mem = {}
def ncr(n,r):
    if (n,r) in mem:
        return mem[(n,r)]
    else:
        ret = mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))
        mem[(n,r)] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp = mul(tmp, ncr(N, red+green+blue))
        tmp = mul(tmp, ncr(red+green+blue, green+blue))
        tmp = mul(tmp, ncr(green+blue, blue))
        ans += tmp
print(ans % MOD)


### FIXED CODE ###

N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

mem = [0] * (N+1)
def ncr(n,r):
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])
        mem[r] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    if b > N: continue
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))  
a = 1
for i in range(N):
  a = a*A[i] 
if (a > 10**18):
  	a = -1
print(a)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
wa = 1
ka = 0
if(a.count(0)>=1):
  print(0)
  ka +=1
else:
  for i in range(n):
    wa = wa*a[i]
    if(wa>10**18):
      print("-1")
      ka +=1
      break
if(ka==0):
  print(wa)
### BUGGY CODE ###

I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))


### FIXED CODE ###

I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())

l = list(map(int, input().split()))
l = sorted(l)

res = 0
for i in range(n):
    for j in range(i, n):
        if i!=j:
            ab = l[i]+l[j]
            for k in range(j, n):
                if i!=k and j!=k and l[k] < ab:
                    res += 1
print(res)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i in range(N):
    for j in range(i+1, N):
        idx = bisect_left(L, L[i]+L[j])
        res += max(0,idx-(j+1))
print(res)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
count_dict = {}
for s in S:
  if not s in count_dict.keys():
    count_dict[s] = 1
  else:
    count_dict[s] += 1
count_dict = dict(filter(lambda x: x[1] == max(count_dict.values()), count_dict.items()))
ans = list(count_dict.keys())
ans.sort()
for s in ans:
  print(s)

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]
count_dict = {}
for s in S:
  if not s in count_dict.keys():
    count_dict[s] = 1
  else:
    count_dict[s] += 1
maxnum = max(count_dict.values())
count_dict = dict(filter(lambda x: x[1] == maxnum, count_dict.items()))
ans = list(count_dict.keys())
ans.sort()
for s in ans:
  print(s)
### BUGGY CODE ###

a,b,x=map(int,input().split())
ans=0
for i in range(b-a+1):
  if (a+i)%x==0:
    ans+=1
print(ans)

### FIXED CODE ###

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

def f(a, x):
    a.append(x)
    a.sort()
    i = a.index(x)
    if 0 > i - 1:
        return a[i + 1]
    if i + 1 >= len(a):
        return a[i - 1]
    if a[i] - a[i - 1] > a[i + 1] - a[i]:
        return a[i + 1]
    return a[i - 1]


def main():
    A, B, Q = map(int, input().split())
    s = []
    t = []
    ans = []
    for _ in range(A):
        s.append(int(input()))
    for _ in range(B):
        t.append(int(input()))
    for _ in range(Q):
        x = int(input())
        sx = f(s[::], x)
        tsx = f(t[::], sx)
        tx = f(t[::], x)
        stx = f(s[::], tx)
        ans.append(min(abs(sx - x) + abs(sx - tsx),
                       abs(tx - x) + abs(tx - stx)))
    for a in ans:
        print(a)


main()


### FIXED CODE ###

import bisect

def main():
    A, B, Q = map(int, input().split())
    s = [-float('inf')]
    t = [-float('inf')]
    ans = []
    for _ in range(A):
        s.append(int(input()))
    for _ in range(B):
        t.append(int(input()))
    s.append(float('inf'))
    t.append(float('inf'))
    for _ in range(Q):
        x = int(input())
        i = bisect.bisect_right(s, x)
        j = bisect.bisect_right(t, x)
        a = float('inf')
        for ss in [s[i - 1], s[i]]:
            for tt in [t[j - 1], t[j]]:
                a = min(a, abs(ss - x) + abs(tt - ss),
                        abs(tt - x) + abs(ss - tt))
        ans.append(a)
    for a in ans:
        print(a)


main()
### BUGGY CODE ###

S=input()
Q=int(input())
cnt=True
for i in range(Q):
    query_list=input().split()
    if query_list[0] == "1":
        cnt=(cnt==False)
    else:
        if cnt:
            if query_list[1] == "1":
                S=query_list[2]+S
            else:
                S+=query_list[2]
        else:
            if query_list[1] == "1":
                S+=query_list[2]
            else:
                S=query_list[2]+S
if cnt:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque
S = deque(input().rstrip())
Q=int(input())
cnt=True
for i in range(Q):
    query_list=input().split()
    if query_list[0] == "1":
        cnt=(cnt==False)
    else:
        if cnt:
            if query_list[1] == "1":
                S.appendleft(query_list[2])
            else:
                S.append(query_list[2])
        else:
            if query_list[1] == "1":
                S.append(query_list[2])
            else:
                S.appendleft(query_list[2])
if cnt:
    print("".join(S))
else:
    print("".join(reversed(S)))
### BUGGY CODE ###

a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
if v<=w:
    print("NO")
    exit()
if a<b:
    for i in range(t):
        a+=v
        b+=w
        if a>=b:
            print("YES")
            exit()
    print("NO")
    exit()
elif a>b:
    for i in range(t):
        a-=v
        b-=w
        if a<=b:
            print("YES")
            exit()
    print("NO")
    exit()
else:
    print("YES")
    exit()

### FIXED CODE ###

a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
if v<=w:
    print("NO")
    exit()
if a<b:
    a+=(v*t)
    b+=(w*t)
    if a>=b:
       print("YES")
       exit()
    print("NO")
    exit()
else:
    a-=(v*t)
    b-=(w*t)
    if a<=b:
        print("YES")
        exit()
    print("NO")
    exit()
### BUGGY CODE ###

import sys
import numpy as np
N,M = list(map(int,sys.stdin.readline().split()))
S = np.array(sys.stdin.readline().split())
#S = [0] + S
T = np.array(sys.stdin.readline().split())
#T = [0] + T
DP = np.zeros((M+1,N+1))
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
mod = 10**9 + 7
for n in range(1,N+1):
    for m in range(1,M+1):
        num = DP[m-1][n-1] if S[n-1] == T[m-1] else 0
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + num - DP[m-1][n-1]) % mod
print(int(DP[M][N]))

### FIXED CODE ###

N,M = list(map(int,input().split()))
S = list(map(int,input().split()))
S = [0] + S
T = list(map(int,input().split()))
T = [0] + T
dp = [[0] * (N+1)  for _ in range(M+1)]
DP = [[0] * (N+1)  for _ in range(M+1)]
dp[0][0] = 1
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
for n in range(1,N+1):
    for m in range(1,M+1):
        if S[n] == T[m]:
            dp[m][n] = DP[m-1][n-1]
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + dp[m][n] - DP[m-1][n-1]) % (10**9+7)
print(DP[M][N])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L_most = {}
J = [[] for _ in range(max(ball)+2)]
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L_most:
    L_most[b]=i
    h.add(i+1,1)
    on.add(i+1)
  J[b].append(i)
    
for i in range(max(ball)+2):
  for j in range(len(J[i])):
    if j+1<len(J[i]):
      jump[J[i][j]+1] = J[i][j+1]+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}
#print(on)

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

for q in LOO:
  print(ans[q])
  
  
  

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on.add(i+1)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

p = []
for q in LOO:
  p.append(ans[q])
  
print(*p, sep="\n")
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
b=list()
for i in range(n):
    b.append(a[i])
    b.reverse()
for i in b:
    print(i,end=' ')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list()
c = list()
for i in range(n):
    if(i==0):
        b.append(a[i])
    elif(i%2==1):
        b.append(a[i])
    else:
        c.append(a[i])
c.reverse()
c = c + b
if(i%2==1):
    c.reverse()
for i in c:
    print(i,end=' ')
### BUGGY CODE ###

N=int(input())
Z=[list(map(int,input().split())) for i in range(N)]
A,B=zip(*Z)
A=list(A[::-1])
B=list(B[::-1])
ans=0
for i in range(N):
  A[i]+=ans
  while A[i]%B[i]!=0:
    ans+=1
    A[i]+=1
print(ans)

### FIXED CODE ###

N=int(input())
Z=[list(map(int,input().split())) for i in range(N)]
A,B=zip(*Z)
A=list(A[::-1])
B=list(B[::-1])
ans=0
for i in range(N):
  A[i]+=ans
  if A[i]%B[i]!=0:
    a=B[i]-(A[i]%B[i])
    ans+=a
print(ans)
### BUGGY CODE ###

S = input()[::-1]

a = [0] * 13
n = [0] * 13

def calc(d, num):
#    shift = (num * (10 ** d))%13
    shift = num
    for _ in range(d):
        shift *= 10
        shift %= 13
    if d==0:
        n[shift] = 1
    else:
        for i in range(13):
            n[(i+shift)%13] += a[i]
    

for d, s in enumerate(S):
    if s=='?':
        for i in range(10):
            calc(d, i)
    else:
        calc(d, int(s[0]))
    a, n = n, a
    for i in range(13):
        a[i] %= 1000000007
        n[i] = 0

print(a[5])





### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    S = input()
    d = 1
    dp = [0] * 13
    dp[0] = 1
    dp_n = [None] * 13
    for s in reversed(S):
        for i in range(13):
            dp[i] %= N1097
            dp_n[i] = 0
        if s == '?':
            for s in range(10):
                diff = (s*d) % 13
                for i in range(13):
                    dp_n[(i+diff)%13] += dp[i]
        else:
            s = int(s)
            diff = (s*d) % 13
            for i in range(13):
                dp_n[(i+diff)%13] += dp[i]
        dp_n, dp = dp, dp_n
        d = (10 * d) % 13
    print(dp[5] % N1097)

main()
### BUGGY CODE ###

def main():
    h, w = list(map(int, input().split()))
    grid = []
    for _ in range(h):
        grid.append(input())

    L = [[0 for _ in range(w)] for _ in range(h)]
    R = [[0 for _ in range(w)] for _ in range(h)]
    D = [[0 for _ in range(w)] for _ in range(h)]
    U = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                continue
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1

    for i in range(h):
        for j in range(w - 1, -1, -1):
            if grid[i][j] == '#':
                continue
            if j == w - 1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j + 1] + 1

    for j in range(w):
        for i in range(h):
            if grid[i][j] == '#':
                continue
            if i == 0:
                D[i][j] = 1
            else:
                D[i][j] = D[i - 1][j] + 1

    for j in range(w):
        for i in range(h - 1, -1, -1):
            if grid[i][j] == '#':
                continue
            if i == h - 1:
                U[i][j] = 1
            else:
                U[i][j] = U[i + 1][j] + 1

    score = 0
    for i in range(h):
        for j in range(w):
            score = max(score, L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3)

    print(score)


main()

### FIXED CODE ###

import numpy as np


def main():
    h, w = list(map(int, input().split()))
    grid = []
    for _ in range(h):
        grid.append(list(input()))

    grid = np.array(grid) == '.'
    # print(grid)

    L = np.zeros((h, w), dtype=int)
    R = np.zeros((h, w), dtype=int)
    D = np.zeros((h, w), dtype=int)
    U = np.zeros((h, w), dtype=int)

    for i in range(1, h):
        U[i] = (U[i - 1] + 1) * grid[i - 1]
        # print(U[i])
    # print(U)

    for i in reversed(range(h - 1)):
        D[i] = (D[i + 1] + 1) * grid[i + 1]

    for j in range(1, w):
        L[:, j] = (L[:, j - 1] + 1) * grid[:, j - 1]
        # print(L[:, j])
    # print(L)

    for j in reversed(range(w - 1)):
        R[:, j] = (R[:, j + 1] + 1) * grid[:, j + 1]

    score = ((U + D + L + R) * grid).max() + 1
    print(score)


main()
### BUGGY CODE ###

def solve():
    import heapq
    from sys import stdin
    h,w = map(int,input().split())
    si,sj = map(int,input().split())
    gi,gj = map(int,input().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    readline = stdin.readline
    for _ in [0]*h:
        grid.append(readline())
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    dist[si][sj] = 0
    heap = [(0,si,sj)]
    while heap:
        mindist,i,j = heapq.heappop(heap)
        if (i,j) == (gi,gj):
            return mindist
        if mindist > dist[i][j]: continue
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    heapq.heappush(heap,(dist[ni][nj],ni,nj))
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in range(j-2,j+3):
                if not (0 <= nj and nj < w): continue
                if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                    if dist[ni][nj] > dist[i][j] + 1:
                        dist[ni][nj] = dist[i][j] + 1
                        heapq.heappush(heap,(dist[ni][nj],ni,nj))
    return -1
print(solve())

### FIXED CODE ###

from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())
### BUGGY CODE ###

import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[sys.maxsize]*n
dp[0]=0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j<n:
            dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]))
print(dp[n-1])


### FIXED CODE ###

import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[sys.maxsize]*n
dp[0]=0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j<n:
            dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]))
print(dp[n-1])