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

n,m=map(int,input().split())
dp=[0]*(m+2)

for i in range(n):  #商品を一つずつ見ていく。
  w,v=(map(int,input().split()))
  for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
    if (dp[j-w]+v)>dp[j]:
      dp[j]=dp[j-w]+v
    else:
      dp[j]=dp[j]
    
print(dp[m+1])




### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

# 整数の入力
N = int(input())
# 計算1
p = 1
 
for num in range(1,N+1):
    p = p * num
    
# 計算2
temp = 10**9 + 7
ans = p % temp
 
# 出力
print(ans)

### FIXED CODE ###

# 整数の入力
N = int(input())
# 計算1
p = 1
temp = 10**9 + 7
 
for num in range(1,N+1):
    p = p * num
    if p > (10**9 + 7):
        p = p % temp
    
# 計算2
ans = p % temp
 
# 出力
print(ans)
### BUGGY CODE ###

import fractions
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
count=a[0]
for i in range(n-1):
    count=count*a[i+1]//fractions.gcd(count, a[i+1])
ans=0
for i in range(n):
    ansa=count//a[i]
    ans+=ansa
    ans%=mod
print(ans)

### FIXED CODE ###

import fractions
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

count=a[0]
for i in range(n-1):
    count=lcm(count,a[i+1])
ans=0
for i in range(n):
    ansa=count//a[i]
    ans+=ansa
    
print(ans%mod)
### BUGGY CODE ###

n=int(input())

ans = 0
for i in range(1,n):
    ans += i

print(ans)   

### FIXED CODE ###

n=int(input())

print(n*(n-1)//2)
### BUGGY CODE ###

n, k = map(int, input().split())

while abs(n-k) < n:
    n = abs(n-k)

print(n)

### FIXED CODE ###

n, k = map(int, input().split())

n = n % k

while abs(n-k) < n:
    n = abs(n-k)

print(n)
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
for i in range(1, min(n+1, b+1)):
    s = int(((a*i)/b) // 1 - a * ((i/b)//1))
    if s > ans:
        ans = s
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
s = min(b-1, n)
ans = int(((a*s)/b) // 1 - a * ((s/b)//1))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    A=lispin()
    sumA=[sum(A[:i+1])for i in range(N)]
    #print(sumA)
    ans=2020202020
    for i in range(N):
        ans=min(ans,abs((sumA[-1]-sumA[i])-sumA[i]))
    print(ans)
#%%submit!
resolve()

### FIXED CODE ###

#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    A=lispin()
    temp=0
    sumA=[0]*N
    sumA[0]=A[0]
    for j in range(1,N):
        sumA[j]=sumA[j-1]+A[j]
    #print(sumA)
    ans=2**32-1
    t=sumA[-1]
    for i in range(N):
        ans=min(ans,abs(t-sumA[i]*2))
        
    print(ans)
#%%submit!
resolve()
### BUGGY CODE ###

from collections import deque
from bisect import bisect

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
R_A = deque()
R_A.append(0)
i = 0
while i < N:
  R_A.append(R_A[-1]+A[i])
  i += 1 
B = list(map(int, input().split()))
R_B = deque()
R_B.append(0)
i = 0
while i < M:
  R_B.append(R_B[-1]+B[i])
  i += 1 
R_B = list(R_B)
ans = 0
i = 0
while i <= N:
  m = K - R_A[i]
  if m < 0:
    break
  idx = bisect(R_B, m)
  ans = max(ans, i+idx-1)
  R_B = R_B[:idx+1]
  i += 1
print(ans)



### FIXED CODE ###

from bisect import bisect

N, M, K = map(int, input().split())
A = [0]+list(map(int, input().split()))
B = list(map(int, input().split()))
R_B = [0]*(M+1)
i = 0
while i < M:
  R_B[i+1] = R_B[i]+B[i]
  i += 1 
ans = 0
i = 0
while i <= N and K >= A[i]:
  K -= A[i]
  idx = bisect(R_B, K)
  ans = max(ans, i+idx-1)
  i += 1
print(ans)
### BUGGY CODE ###

import sys

icase=0
if icase==0:
    n=int(input())
    a=[[0]*n for i in range(n)]
    for i in range(n):
        a[i]=list(map(int,input().split()))
elif icase==1:
    n=3
    a=[[0, 1, 3], [1, 0, 2], [3, 2, 0]]
#    a=[[0, 1, 3], [1, 0, 1], [3, 1, 0]]

dp=[[0]*n for i in range(n)]
for i in range(n):
    dp[i]=a[i].copy()
    
c=[[0]*n for i in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dp[i][j]>dp[i][k]+dp[k][j]:
                dp[i][j]=dp[i][k]+dp[k][j]
            if dp[i][j]==dp[i][k]+dp[k][j] and i!=k and j!=k:
                c[i][j]=1                
                

icnt=0
for i in range(0,n-1):
    for j in range(i+1,n):
        if a[i][j]!=dp[i][j]:
            print(-1)
            sys.exit()
        elif c[i][j]==0:
            icnt+=dp[i][j]
print(icnt)

### FIXED CODE ###

import sys

icase=0
if icase==0:
    n=int(input())
    a=[[0]*n for i in range(n)]
    for i in range(n):
        a[i]=list(map(int,input().split()))
elif icase==1:
    n=3
    a=[[0, 1, 3], [1, 0, 2], [3, 2, 0]]
#    a=[[0, 1, 3], [1, 0, 1], [3, 1, 0]]

dp=[[0]*n for i in range(n)]
for i in range(n):
    dp[i]=a[i].copy()
    
c=[[0]*n for i in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dp[i][j]>dp[i][k]+dp[k][j]:
                dp[i][j]=dp[i][k]+dp[k][j]
            if dp[i][j]==dp[i][k]+dp[k][j] and i!=k and j!=k:
                c[i][j]=1                
                

icnt=0
for i in range(0,n-1):
    for j in range(i+1,n):
        if a[i][j]!=dp[i][j]:
            print(-1)
            sys.exit()
        elif c[i][j]==0:
            icnt+=dp[i][j]
print(icnt)
### BUGGY CODE ###

N = int(input())
A = list((i, j) for i, j in enumerate(map(int, input().split())))
un = sorted(A, reverse=True)

ans = 0

for i in range(N):
    un = un[0:-1]
    ans += len(tuple(filter(lambda x:x[0]-i == x[1]+A[i][1], un)))

print(ans)

### FIXED CODE ###

N = int(input())
A = list((i, j) for i, j in enumerate(map(int, input().split())))
dictL = {}
dictR = {}

ans = 0
for i in range(N):
    l, r = A[i][1] + A[i][0], A[i][0] - A[i][1]
    if l not in dictL:
        dictL[l] = 1
    else:
        dictL[l] += 1
    if r not in dictR:
        dictR[r] = 1
    else:
        dictR[r] += 1

for i in dictL.keys():
    if i in dictR.keys():
        ans += dictL[i] * dictR[i]
        
print(ans)
### BUGGY CODE ###

n, c, k = map(int, input().split())
tList = [int(input()) for _ in range(n)]
tList.sort()
count = 0
while 1:
    limit = tList[0] + k
    last = min(c, len(tList))
    if tList[last - 1] <= limit:
        mark = last - 1
    else:
        for i in range(last):
            if tList[i] > limit:
                break
            mark = i
    count += 1
    tList = tList[mark + 1:]
    if tList == []:
        break
print(count)

### FIXED CODE ###

def boundary_find(array, limit):
    ceil = len(array) - 1 
    floor = 0
    while 1:
        center = (ceil + floor) // 2
        if array[center] <= limit:
            floor = center
        else:
            ceil = center
        if ceil - floor == 1:
            break
    return ceil

n, c, k = map(int, input().split())
tList = [int(input()) for _ in range(n)]
tList.sort()
count = 0
first = 0
while 1:
    limit = tList[first] + k
    last = min(first + c, n)
    if tList[last - 1] <= limit:
        mark = last
    else:
        mark = boundary_find(tList, limit)
    count += 1
    first = mark
    if first == n:
        break
print(count)
### BUGGY CODE ###

def binary_search_ceiling(list, element):
    i = 0
    j = len(list) - 1
    if element < list[0]:
        return None
    elif element >= list[-1]:
        return len(list) - 1
    while i <= j:
        k = (i + j) // 2
        if list[0] == element:  # k - 1が0にならないので特例
            return 0
        elif list[k - 1] < element <= list[k]:
            return k
        elif list[k] < element < list[k + 1]:
            return k + 1
        elif list[k] < element:
            i = k  # elementがk番とk+1番の間にあるかもしれないのでi = k + 1 ではなくi = k
        else:
            j = k  # 上と同様に考えてj = k

    return None


def main():
    A, B, Q = map(int, input().split())
    INF = 10 ** 11
    s_list = [-2 * INF, -INF] + [int(input()) for i in range(A)] + [INF, 2 * INF]
    t_list = [-2 * INF, -INF] + [int(input()) for i in range(B)] + [INF, 2 * INF]
    x_list = [int(input()) for i in range(Q)]

    for xi in x_list:
        ind_s = binary_search_ceiling(s_list, xi)
        ws = s_list[ind_s - 1]
        es = s_list[ind_s]

        ind_t = binary_search_ceiling(t_list, xi)
        wt = t_list[ind_t - 1]
        et = t_list[ind_t]

        dist = min(
                     xi - min(ws, wt),
                     max(es, et) - xi,
                     xi + es - wt * 2,
                     xi + et - ws * 2,
                     (es * 2) - wt - xi,
                     (et * 2) - ws - xi
                     )

        print(dist)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect as b


def main():
    A, B, Q = map(int, input().split())
    INF = 10 ** 11
    s_list = [-INF] + [int(input()) for i in range(A)] + [INF]
    t_list = [-INF] + [int(input()) for i in range(B)] + [INF]

    len_s = A + 1
    len_t = B + 1

    for i in range(Q):
        xi = int(input())
        ind_s = b.bisect_left(s_list, xi)
        ws = s_list[ind_s - 1]
        es = s_list[ind_s]

        ind_t = b.bisect_left(t_list, xi)
        wt = t_list[ind_t - 1]
        et = t_list[ind_t]

        dist_list = [
                     xi - min(ws, wt),
                     max(es, et) - xi,
                     xi + es - wt * 2,
                     xi + et - ws * 2,
                     (es * 2) - wt - xi,
                     (et * 2) - ws - xi
                     ]

        print(min(dist_list))


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

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    def to_3(num):
        s = []
        while num > 0:
            s.append(str(num % 3))
            num //= 3
        return "{:0>15}".format("".join(s[::-1]))

    answer = [10**18] * (N+1)
    for bit in range(pow(3, N)):
        bit_S = to_3(bit)[-N:]
        x_bit = 0
        y_bit = 0
        x_set = set()
        y_set = set()
        for i in range(N):
            if bit_S[i] == "2":
                # x = a
                x_bit += pow(2, i)
                x_set.add(T[i][0])
            elif bit_S[i] == "1":
                # y = a
                y_bit += pow(2, i)
                y_set.add(T[i][1])
        cnt = len(x_set) + len(y_set)
        # 距離の評価
        cur_d = 0
        for i in range(N):
            cur_d += min(X_dist[x_bit][i], Y_dist[y_bit][i])
        answer[cnt] = min(answer[cnt], cur_d)

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        a, b, c = (int(i) for i in input().split())
        X.append(a)
        Y.append(b)
        P.append(c)
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        for i in range(N):
            X_dist[bit][i] = P[i]*abs(X[i])
            Y_dist[bit][i] = P[i]*abs(Y[i])
            for k in range(N):
                if bit & (1 << k):
                    X_dist[bit][i] = \
                        min(X_dist[bit][i], P[i]*abs(X[i] - X[k]))
                    Y_dist[bit][i] = \
                        min(Y_dist[bit][i], P[i]*abs(Y[i] - Y[k]))

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


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

n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]
global ans
ans = sum([a, b, c])
def count(a_use, b_use, c_use, non_use):
  global ans
  if a_use and b_use and c_use:
    cost = abs(sum(a_use)-a)+abs(sum(b_use)-b)+abs(sum(c_use)-c) + 10*((len(a_use)-1) + (len(b_use)-1) +(len(c_use)-1) )
    ans = min(cost, ans)
  for i in range(len(non_use)):
    temp = non_use[:]
    temp.pop(i)
    use = [non_use[i]]
    count(a_use+use, b_use, c_use, temp)
    count(a_use, b_use+use, c_use, temp)
    count(a_use, b_use, c_use+use, temp)
    count(a_use, b_use, c_use, temp)
count([], [], [], l)
print(ans)

### FIXED CODE ###

n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]
INF = 10**9
def count(a_sum, b_sum, c_sum, cur):
  if cur == n:
    return (abs(a_sum -a) + abs(b_sum -b) +abs(c_sum -c)) -30 if min(a_sum, b_sum, c_sum) > 0 else INF
  else:
    ans1 = count(a_sum, b_sum, c_sum, cur+1)
    ans2 = count(a_sum+l[cur], b_sum, c_sum, cur+1) + 10 
    ans3 = count(a_sum, b_sum+l[cur], c_sum, cur+1) + 10
    ans4 = count(a_sum, b_sum, c_sum+l[cur], cur+1) + 10
    return min(ans1, ans2, ans3, ans4)

print(count(0, 0, 0, 0))
### BUGGY CODE ###

mod = 10**9+7
def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()


### FIXED CODE ###

mod = 10**9+7
def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()
### BUGGY CODE ###

import sys

n = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
ans = 0
for i in range(len(lst)):
    ans += lst[i] * sum(lst[i+1:])

print(ans%(10**9+7))

### FIXED CODE ###

import sys

n = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))

pref = [lst[0]]
for i in range(1, len(lst)):
    pref.append(pref[i-1]+lst[i])

ans = 0
for i in range(len(lst)):
    ans += lst[i] * (pref[-1] - pref[i])

print(ans%(10**9+7))
### BUGGY CODE ###

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

ans = 1e15

"""
abcdef
f +4(f-e) + 9+(e-d) + 16(d-c) + ...
= 5f + 5e + 7d + 9c + 11b + 13a
"""
mul = [5] + [5 + 2*i for i in range(N)]
#print(mul)

for k in range(1,N+1): # Number of robots
  cost = N*X + k*X # pickup and throw costs(fixed with k)
  for i in range(1,N+1):
    cost += A[N-i] * mul[(i-1)//k]
  #print(k,cost)
  ans = min(ans,cost)
  
print(ans)
  
  

### FIXED CODE ###

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

ans = 1e19

"""
abcdef
f +4(f-e) + 9+(e-d) + 16(d-c) + ...
= 5f + 5e + 7d + 9c + 11b + 13a
"""
mul = [5] + [5 + 2*i for i in range(N)]
#print(mul)

CX = [0] * (N+1)

#cum_sum
for i in range(N):
  CX[i+1] = CX[i] + A[i]
  
for k in range(1,N+1): # Number of robots (this loop will be ended early)
  cost = N*X + k*X # pickup and throw costs(fixed with k)
  
  # partial point answer (not using cumulative sum)
  # for i in range(1,N+1):
  #  cost += A[N-i] * mul[(i-1)//k]
  ix = N
  loopc = 0
  while ix > 0:
    if ix-k > 0:
      cost += (CX[ix] - CX[ix-k]) * mul[loopc]
    else:
      cost += (CX[ix]) * mul[loopc]
    loopc += 1
    ix -= k
  
  #print(k,cost)
  ans = min(ans,cost)
  if N//k <= 1: # early stopping (after mul is 5 for all A's, cost is monotonicaly increasing)
    print(ans)
    exit(0)
    
#print(ans)
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N,K = MI()

A = LI()

multi = {}

start = 1
for k in range(0,K):
    start = start * A[k]
for j in range(K, N+1):
    if j == K:
        multi[j] = start
        continue
    start = start // A[j-K-1] * A[j-1]
    multi[j] = start
    
for i in range(K, N+1):
    if i-1 in multi:
        if multi[i] > multi[i-1]:
            print("Yes")
        else:
            print("No")

### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N,K = MI()

A = LI()

for j in range(K, N+1):
    if j == K:
        continue
    if A[j-K-1] < A[j-1]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

for i in range(n-1):
    a[0] = a[0] * a[i+1]

if a[0] > 10 ** 18:
    print('-1')
else:
    print(a[0])


### FIXED CODE ###

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

if 0 in a:
    ans = 0
else:
    ans = 1
    for i in range(n):
        ans = ans * a[i]
        if ans > 10 ** 18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
x, y = map(int, input().split())

if x==y:
    print(-1)
    exit()

if y==1:
    print(-1)
    exit()

ans = x
while ans<10**18:
    if x%y!=0:
        print(x)
        exit()
    else:
        ans+=x


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
x, y = map(int, input().split())

if x%y==0:
    print(-1)
    exit()

ans = x
while ans<=10**18:
    if x%y!=0:
        print(x)
        exit()
    else:
        ans+=x
### BUGGY CODE ###

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

costs = [999999999999999999] * N
costs[0] = 0
for i in range(N-1):
    for j in range(i, min(N, i+K+1)):
        costs[j] = min(costs[j],
                       costs[i]+abs(hs[j]-hs[i]))
print(costs[-1])

### FIXED CODE ###

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

costs = [999999999999999999] * N
costs[0] = 0
for i in range(N-1):
    for j in range(i, min(N, i+K+1)):
        costs[j] = min(costs[j],
                       costs[i]+abs(hs[j]-hs[i]))
print(costs[-1])
### BUGGY CODE ###

h, w = map(int, input().split())
lst = [[0] for _ in range(h)]
for i in range(h):
    tmp = list(input())
    lst[i] = tmp

H = [[0] * w for _ in range(h)]
W = [[0] * w for _ in range(h)]

for i in range(h):
    done = [0] * w
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if done[j]:
            continue
        k = 0
        while lst[i][j+k] != '#':
            done[j+k] = 1
            k += 1  # kが照らせるマスの長さ
            if j+k > w-1:
                break
        for l in range(k):
            H[i][j+l] = k


for j in range(w):
    done = [0] * h
    for i in range(h):
        if lst[i][j] == '#':
            continue
        if done[i]:
            continue
        k = 0
        while lst[i+k][j] != '#':
            done[i+k] = 1
            k += 1  # kが照らせるマスの長さ
            if i+k > h-1:
                break
        for l in range(k):
            W[i+l][j] = k

ans = 0
for i in range(h):
    for j in range(w):
        if lst[i][j] != '#':
            ans = max(ans, H[i][j] + W[i][j] - 1)

print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
lst = [[0] for _ in range(h)]
for i in range(h):
    tmp = list(input())
    lst[i] = tmp

H = [[0] * w for _ in range(h)]
W = [[0] * w for _ in range(h)]

for i in range(h):
    done = [0] * w
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if done[j]:
            continue
        k = 0
        while lst[i][j+k] != '#':
            done[j+k] = 1
            k += 1  # kが照らせるマスの長さ
            if j+k > w-1:
                break
        for l in range(k):
            H[i][j+l] = k


for j in range(w):
    done = [0] * h
    for i in range(h):
        if lst[i][j] == '#':
            continue
        if done[i]:
            continue
        k = 0
        while lst[i+k][j] != '#':
            done[i+k] = 1
            k += 1  # kが照らせるマスの長さ
            if i+k > h-1:
                break
        for l in range(k):
            W[i+l][j] = k

ans = 0
for i in range(h):
    for j in range(w):
        if lst[i][j] != '#':
            ans = max(ans, H[i][j] + W[i][j] - 1)

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

n,X = map(int,input().split())
x =list(map(int,input().split()))
x.append(X)
x.sort()
a = []
for i in range(n):
  a.append(x[i+1]-x[i])
  
g = []
h = min(a)
for i in range(h,0,-1):
  if h%i == 0:
    g.append(i)
    
gcd = 1
for i in g:
  if all(a[j]%i == 0 for j in range(n)) :
    gcd = i
    break
    
    
print(gcd)
    
  
  




### FIXED CODE ###

n,X = map(int,input().split())
x =list(map(int,input().split()))
x.append(X)
x.sort()
a = []
for i in range(n):
  a.append(x[i+1]-x[i])
  
h = min(a)
gcd = 1
for i in range(h,0,-1):
  if h%i == 0:
    if all(a[j]%i == 0 for j in range(n)):
      gcd = i
      break
      
print(gcd)