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

from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
def S(): return stdin.readline().rstrip()
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def BFS(table,s,step,next,w,h):
    if table[h-1][w-1] != -2:
        return
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    nnext = []
    for rep in next:
        for j in range(4):
            nx = rep[0] + dx[j]
            ny = rep[1] + dy[j]
            if nx<0  or ny<0 or w<=nx or h<=ny:
                continue
            else:
                if s[ny][nx]=='#':
                    continue
                if table[ny][nx]==-2 or step+1<table[ny][nx]:
                    table[ny][nx] = step+1
                    nnext.append([nx,ny])
    BFS(table,s,step+1,nnext,w,h)

def main():
    tmp = LI()
    w,h = tmp.pop(),tmp.pop()
    s = [S() for _ in range(h)]
    table = [[-2]*w for _ in range(h)]
    BFS(table,s,0,[[0,0]],w,h)
    step = table[h-1][w-1]
    c = 0
    for rep in s:
        c += rep.count('#')
    ans = w*h-step-c-1
    print(ans)
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
def S(): return stdin.readline().rstrip()
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def BFS(table,s,step,next,w,h):
    if table[h-1][w-1] != -2:
        return
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    nnext = []
    for rep in next:
        for j in range(4):
            nx = rep[0] + dx[j]
            ny = rep[1] + dy[j]
            if nx<0  or ny<0 or w<=nx or h<=ny:
                continue
            else:
                if s[ny][nx]=='#':
                    continue
                if table[ny][nx]==-2 or step+1<table[ny][nx]:
                    table[ny][nx] = step+1
                    nnext.append([nx,ny])
    if 0<len(nnext):
        BFS(table,s,step+1,nnext,w,h)

def main():
    tmp = LI()
    w,h = tmp.pop(),tmp.pop()
    s = [S() for _ in range(h)]
    table = [[-2]*w for _ in range(h)]
    BFS(table,s,0,[[0,0]],w,h)
    step = table[h-1][w-1]
    if step==-2:
        print(-1)
        exit()
    c = 0
    for rep in s:
        c += rep.count('#')
    ans = w*h-step-c-1
    print(ans)
    return

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

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

def solve():
    """ dp[i+k]を求める方法
    TLE 
    """
    N,K=list(map(int,input().split()))
    A=list(map(int,input().split()))
    
    INF=float("inf")
    
    dp=[INF]*N
    dp[0]=0
    
    for i in range(0, N-1):
        for k in range(1, K+1):
            if i+k <= N-1:
                dp[i+k]=min(dp[i+k],dp[i]+abs(A[i]-A[i+k]))
            else:
                break
    print(dp[N-1])

def solve2():
    """dp[i]を求める方法
    """
    N,K=list(map(int,input().split()))
    A=list(map(int,input().split()))
    
    INF=float("inf")
    
    dp=[INF]*N
    dp[0]=0
    for i in range(1, N):
        for k in range(1, K+1):
            if i-k >= 0:
                dp[i] = min(dp[i], dp[i-k]+abs(A[i]-A[i-k]))
            else:
                break
    print(dp[N-1])


if __name__ == "__main__":
    solve2()


### FIXED CODE ###

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

def solve():
    """ dp[i+k]を求める方法
    TLE 
    """
    N,K=list(map(int,input().split()))
    A=list(map(int,input().split()))
    
    INF=float("inf")
    
    dp=[INF]*N
    dp[0]=0
    
    for i in range(0, N-1):
        for k in range(1, K+1):
            if i+k <= N-1:
                dp[i+k]=min(dp[i+k],dp[i]+abs(A[i]-A[i+k]))
            else:
                break
    print(dp[N-1])


def solve2():
    """dp[i]を求める方法
    """
    N,K=list(map(int,input().split()))
    A=list(map(int,input().split()))
    
    INF=float("inf")
    
    dp=[INF]*N
    dp[0]=0
    for i in range(1, N):
        for k in range(1, K+1):
            if i-k >= 0:
                dp[i] = min(dp[i], dp[i-k]+abs(A[i]-A[i-k]))
            else:
                break
    print(dp[N-1])


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

n=int(input())
a=list(map(int,input().split()))
import fractions 
mod=pow(10,9)+7
lcma=1
for ai in a:
  lcma*=ai//fractions.gcd(lcma,ai)
ans=0
for ai in a:
  ans+=((lcma//ai))%mod
  ans%=mod
print(ans)


### FIXED CODE ###

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

#n=10000
#a=list(range(10**6,10**6-n,-1))

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
lcma={}
for ai in a:
  f=factorization(ai)
  for fi in f:
    if fi[0] in lcma:
      lcma[fi[0]]=max(lcma[fi[0]],fi[1])
    else:
      lcma[fi[0]]=fi[1]
l=1
for k,v in lcma.items():
  l*=pow(k,v,mod)
  l%=mod
ans=0
for ai in a:
  ans+=l*pow(ai,mod-2,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

import itertools

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

counts = 0
products = itertools.product(A, B, C)
for product in products:
    if(product[0] < product[1] and product[1] < product[2]):
        counts += 1
print(counts)


### FIXED CODE ###

import bisect

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

counts = 0
checked = {}
for _numB in B:
    if _numB not in checked:
        countsA = bisect.bisect_left(A, _numB)
        countsC = bisect.bisect_right(C, _numB)
        checked[_numB] = countsA * (N - countsC)
    counts += checked[_numB]
print(counts)
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
A, B = map(int, input().split())

count = 0
tmp = 1

for i in range(1, min(A, B)+1):
    if A%i == 0 and B%i == 0 and gcd(i, tmp) == 1:
        tmp *= i
        count += 1
print(count)


### FIXED CODE ###

from fractions import gcd
A, B = map(int, input().split())
G = gcd(A, B)

# nの[素因数, その数]のリストを返す
def prime_factoring(n):
    from math import sqrt
    factors = []
    for num in range(2, int(sqrt(n))+1):
        if n % num == 0:
            count = 0
            while(n % num == 0):
                n //= num
                count += 1
            factors.append([num, count])
    else:
        if n != 1:
            factors.append(n)
    return factors

print(len(prime_factoring(G))+1)
### BUGGY CODE ###

from heapq import heappop, heappush, heapify

class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)    


N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append([x,i])
    Y.append([y,i])
 
X.sort()
Y.sort()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
uf = UnionFind(N)
 
ans=0
for l,a,b in edge:
    if uf.same(a,b):
        continue
    else:
        uf.union(a,b)
        ans += l
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append([x,i])
    Y.append([y,i])

X.sort()
Y.sort()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
parent=[-1]*N

ans=0
for l,a,b in edge:
    if find_parent(a)==find_parent(b):
        continue
    else:
        ans+=l
        connect(a,b)

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

N = int(input())
A = input()
Q = int(input())
for q in range(Q):
  b, c = input().split()
  A = A.replace(b,c)
  An = list(map(int,A.split()))
  print(sum(An))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
C_A = Counter(A)
S = 0
for ca in C_A:
  S += ca * C_A[ca]

Q = int(input())
for q in range(Q):
  b, c = map(int,input().split())
  S += (c - b) * C_A[b]
  C_A[c] += C_A[b]
  C_A[b] = 0
  
  print(S)
### BUGGY CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    DP = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    DP[0][0][0] = 1

    for i in range(N):
        DP[i + 1][0][0] = DP[i][0][0] 
        DP[i + 1][0][1] = DP[i][0][0] + DP[i][0][1]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP[i + 1][j][1] = DP[i][j][1] #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP[i + 1][j][1] = DP[i][j][1] #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP[i + 1][j][1] = (DP[i][j][1] + DP[i][j - a][0] + DP[i][j - a][1]) % MOD
                # DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i + 1][j - a][1]) % MOD

        DP[i + 1][S][2] = (DP[i][S][1] + DP[i][S][2])
        if a <= S:
            DP[i + 1][S][2] += DP[i][S - a][0] + DP[i][S - a][1]
        DP[i + 1][S][2] %= MOD

    print (DP[N][S][2])

    # for i in range(N + 1):
    #     print (DP[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    DP0 = [[0] * (S + 1) for _ in range(N + 1)]
    DP1 = [[0] * (S + 1) for _ in range(N + 1)]
    DP2 = [[0] * (S + 1) for _ in range(N + 1)]

    DP0[0][0] = 1

    for i in range(N):
        DP0[i + 1][0] = DP0[i][0] 
        DP1[i + 1][0] = DP0[i][0] + DP1[i][0]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP1[i + 1][j] = (DP1[i][j] + DP0[i][j - a] + DP1[i][j - a]) % MOD
                # DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i + 1][j - a][1]) % MOD

        DP2[i + 1][S] = (DP1[i][S] + DP2[i][S])
        if a <= S:
            DP2[i + 1][S] += DP0[i][S - a] + DP1[i][S - a]
        DP2[i + 1][S] %= MOD

    print (DP2[N][S])

    # for i in range(N + 1):
    #     print (DP[i])

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

import sys
sys.setrecursionlimit(10000)
s = input()
x,y = map(int,input().split())
count = s.count('F')
ans = abs(x)+abs(y) <= count
def bfs(x,y,s,count):
    if count < abs(x)+abs(y):
        return False
    elif x==0 and y==0 and s == '':
        return True
    else:
        if s[0] == 'F':
            x -= 1
            s = s[1:]
            count -= 1
            return bfs(x,y,s,count)
        else:
            s = s[1:]
            return bfs(y,-x,s,count) or bfs(-y,x,s,count)
ans = bfs(x,y,s,count)
if ans:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = input()
x,y = map(int,input().split())
count = 0
d = []
s = s.split('T')
d = [len(x) for x in s]

if len(d) == 0:
    d.append(0)
if len(d) == 1:
    d.append(0)
dpx = [d[0]]
dpy = [d[1],-d[1]]
for i in range(2,len(d)):
    di = d[i]
    trans = set()
    if i%2==0:
        for xj in dpx:
            trans.add(xj+di)
            trans.add(xj-di)
        dpx = list(trans)
    else:
        for yj in dpy:
            trans.add(yj+di)
            trans.add(yj-di)
        dpy = list(trans)
ans = (x in dpx)&(y in dpy)

if ans:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

a,b,c,d = map(int, input().split())
finish = False

while not finish:
    for i in range(2):
        if i==0:
            c -= b
        elif i==1:
            a-= d
        if a == 0 or c == 0:
            finish = True
            break

if a==0 and c!=0:
    print('No')
elif a!=0 and c==0:
    print('Yes')

### FIXED CODE ###

a,b,c,d = map(int, input().split())

taka1 = a//d
taka2 = a%d
aoki1 = c//b
aoki2 = c%b

if a%d != 0:
    taka1 += 1
if c%b != 0:
    aoki1 += 1

if taka1 >= aoki1:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

S = input()
mod = 10 ** 9 + 7

dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
cnt = 1

for i, s in enumerate(S[::-1]):
    if s == "?":
        tmp = pow(10, i, 13)
        for x in range(13):
            for y in range(10):
                next_x = y * tmp + x
                dp[i+1][next_x % 13] += dp[i][x]
                dp[i+1][next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s)*10**i+x
            dp[i + 1][next_x % 13] = dp[i][x]


ans = dp[-1][5] % mod
print(ans)


### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7

dp = [0]*13
dp[0] = 1

mul = 1
for i, s in enumerate(S[::-1]):
    new = [0]*13
    if s == "?":
        for x in range(13):
            for y in range(10):
                next_x = y * mul + x
                new[next_x % 13] += dp[x]
                new[next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s) * mul + x
            new[next_x % 13] = dp[x]

    dp = new
    mul *= 10
    mul %= 13

ans = dp[5] % mod
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
count = 0

for i in range(len(l)):
    for j in range(i+1,len(l)):
        for k in range(j+1,len(l)):
            if l[i]+l[j]>l[k] and l[j]+l[k]>l[i] and l[k]+l[i]>l[j]:
                count += 1
print(count)

### FIXED CODE ###

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

import bisect
for i in range(len(l)):
    for j in range(i+1,len(l)):
        end = bisect.bisect_left(l,l[i]+l[j])
        start = j
        count += end - start -1
print(count)
### BUGGY CODE ###

import sys

def solve1(s, cache={}):
    n = len(s)
    if n == 1:
        return 1
    r = n
    while 1:
        i = 1
        while i < n:
            if s[i] != s[0]:
                for k in range(i):
                    s[k] = s[i]
                break
            if s[-i-1] != s[-1]:
                for k in range(i):
                    s[-k-1] = s[-i-1]
                break
            i += 1
        if n == i:
            break
        r = min(r, n - i)
    return r


line = sys.stdin.readline().strip()
print(solve1(list(line)))


### FIXED CODE ###

import sys

def solve1(s):
    n = len(s)
    i = 0
    while i <= n // 2:
        if s[n // 2] != s[n // 2 - i]:
            break
        if s[(n - 1) // 2] != s[(n - 1) // 2 + i]:
            break
        i += 1
    return (n - 1) // 2 + i


line = sys.stdin.readline().strip()
print(solve1(list(line)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 0
mod = 10**9+7
for i in range(len(a)-1):
    for j in range(i+1, len(a)):
        t = a[i]*a[j]
        t%=mod
        s += t
        s%=mod
print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
k = 0
b = [0]*len(a)
ans = 0
for i in range(len(a)-1, 0, -1):
    k += a[i]
    k %= mod
    b[i] = k
for i in range(len(a)-1):
    ans += a[i] * b[i+1]
    ans %= mod

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

s = input()

def get_sum(J, I, L, K):
    total1 = int(I * P3[J] + J * P3[J-1])
    total2 = int(K * P3[L] + L * P3[L-1])
    return total1 * total2

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

P3 = [1]
for i in range(1, 10 ** 5):
    P3.append(P3[-1] * 3)

total = 0
for i in range(len(s)):
    if s[i] == '?':
        _n_q_left = n_q - n_q_right[i] - 1
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], n_a_right[i], _n_q_left, _n_c_left) %  (10 ** 9 + 7)
    elif s[i] == 'B':
        _n_q_left = n_q - n_q_right[i]
        _n_c_left = n_c - n_c_right[i]
        total += get_sum(n_q_right[i], n_a_right[i], _n_q_left, _n_c_left) %  (10 ** 9 + 7)



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


### FIXED CODE ###

s = input()
a, d = [0], [0]
for char in s[:-1]:
    if char == 'A':
        a.append(a[-1] + 1)
    else:
        a.append(a[-1])
    if char == '?':
        d.append(d[-1] + 1)
    else:
        d.append(d[-1])

c, e = [0], [0]
for char in s[::-1][:-1]:
    if char == 'C':
        c.append(c[-1] + 1)
    else:
        c.append(c[-1])
    if char == '?':
        e.append(e[-1] + 1)
    else:
        e.append(e[-1])
c = c[::-1]
e = e[::-1]

ret = 0
mod = 10 ** 9 + 7
for char, aa, dd, cc, ee in zip(s, a, d, c, e):
    if char in 'B?':
        tmp1 = aa * pow(3, dd, mod)
        if dd != 0:
            tmp1 += dd * pow(3, dd - 1, mod)

        tmp2 = cc * pow(3, ee, mod)
        if ee != 0:
            tmp2 += ee * pow(3, ee - 1, mod)

        ret += tmp1 * tmp2
        ret %= mod

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

s = input()[::-1]

dataset = [0]*2019
dataset[0] = 1

n = 0
d = 0

for i in s:
    n += int(i) * (10**d)
    a = n % 2019
    dataset[a] += 1
    d += 1

count = 0
for i in dataset:
    count += i * (i-1) // 2

print(count)

### FIXED CODE ###

s = input()[::-1]

dataset = [0]*2019
dataset[0] = 1

n = 0
d = 1

for i in s:
    n += int(i) * d
    a = n % 2019
    dataset[a] += 1
    d *= 10
    d %= 2019

count = 0
for i in dataset:
    count += i * (i-1) // 2

print(count)
### BUGGY CODE ###

totalNumbers=int(input())
array=list(map(int,input().split()))
import math
answer=math.prod(array)
print(-1 if answer>10**18 else answer)


### FIXED CODE ###

totalNumbers = int(input())
array = list(map(int, input().split()))
answer = 1
if 0 in array:
    print(0)
else:
    for number in array:
        answer*=number
        if answer>10**18:
            answer=-1
            break
    print(answer)
### BUGGY CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

n = int(input())
s = [int(input()) for i in range(n)]
ans = 0

def dfs(index, total):
    if index == n:
        if total % 10 != 0:
            global ans
            ans = max(ans, total)
        return
    if s[index] == 0:
        dfs(index + 1, total)
        return
    dfs(index + 1, total + s[index]) or dfs(index + 1, total)

dfs(0, 0)
print(ans)


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n = int(input())
s = [int(input()) for i in range(n)]
if sum(s) % 10 != 0:
    print(sum(s))
else:
    s.sort()
    for i in s:
        if i % 10 != 0:
            print(sum(s) - i)
            break
    else:
        print(0)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    if all(p[i] <= p[j] for j in range(i)):
        ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
p_min = p[0]
for i in range(n):
    if p[i] <= p_min:
        ans += 1
        p_min = p[i]
print(ans)
### BUGGY CODE ###

n, sum_w = map(int, input().split())
weight = []
value = []
for i in range(n):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

dp = [[0] * (sum_w + 1) for i in range(n+1)]

for i in range(n):
    for j in range(sum_w + 1):
        if j < weight[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])

print(dp[-1][-1])


### FIXED CODE ###

n, sum_w = map(int, input().split())
weight = []
value = []
for i in range(n):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

dp = [[0] * (sum_w + 1) for i in range(n+1)]

for i in range(n):
    for j in range(sum_w + 1):
        if j < weight[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])

print(dp[-1][-1])
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
mod = 10**9+7
A.sort()
ans = 0
m = K
d = 1
n = 1
for i in range(K-1, N):
    ans += A[i]*n
    ans -= A[-i-1]*n
    n = n*m//d
    m += 1
    d += 1
    ans %= mod
print(ans)


### FIXED CODE ###

mod = 10**9+7
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
ans = 0
m = K
d = 1
n = 1
for i in range(K-1, N):
    ans += A[i]*n
    ans -= A[-i-1]*n
    n *= pow(d, mod-2, mod)
    n = n*m % mod
    m += 1
    d += 1
    ans %= mod
print(ans)
### 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**7
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,I,J,s):
  dx,dy = dire[di]
  if J == 0:
    if 0 <= x+dx < h and 0 <= y+dy < w:
      if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s+I:
        #print(s+I,'&&',x+dx,y+dy,di)
        now.append([s+I,x+dx,y+dy,di])
        seen[x+dx][y+dy][di] = s+I
  else:
    if seen[x][y][di] > s+I:
      nex.append([s+I,x,y,di])
      seen[x][y][di] = s+I

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)
        #for xx in seen:
          #print(xx)
        exit()
      #print('&',s,x,y,di)
      add(x,y,di,1-int(bool(i)),0,s)
      for d in range(4):
        add(x,y,d,0,1,s)
    #print(now)
  #print('#',nex)
  nex += now
  #print('#',nex)
print(-1)
#for xx in seen:
  #print(xx)

### 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)