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

### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if (i == 0) & (Current_Weight <= W) :
        dp[Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = list(dp.keys())
        for j in Last_Search_List:
            Current_Search_Weight = j + Current_Weight
            if Current_Search_Weight in dp:
                dp[Current_Search_Weight] = max(dp[Current_Search_Weight],
                                                dp[j] + Current_Value)
            elif Current_Search_Weight <= W :
                dp[Current_Search_Weight] = dp[j] + Current_Value

print(max(dp.values()))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_e
import copy
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
 
Sum_Value = sum(map(lambda x:x[1],Goods_List))
dp = [[0] * (Sum_Value + 1) for i in range(N)]

for i in range(N):
    if i == 0:
        dp[i][Goods_List[i][1]] = Goods_List[i][0]
    else:
        dp[i] = copy.copy(dp[i-1])
        Valid_List = [k for k, x in enumerate(dp[i]) if x != 0]
        Valid_List.append(0)
        for j in Valid_List:
            if dp[i][j + Goods_List[i][1]] == 0:
                dp[i][j + Goods_List[i][1]] = dp[i-1][j] + Goods_List[i][0]
            else:
                dp[i][j + Goods_List[i][1]] = min(dp[i-1][j] + Goods_List[i][0],dp[i][j + Goods_List[i][1]])
        

for k in range(len(dp[-1])-1,0,-1):
    if (dp[-1][k] != 0) & (dp[-1][k] <= W):
        print(k)
        break
### BUGGY CODE ###

import scipy.misc as scm

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

b = sorted(a, reverse=True)

for i in b:
    j = 0
    if(i % 2 == 0):
        m = int(i/2)
    else:
        m = int((i+1)/2)
    while(True):
        if(int(m - j) in b):
            print("%d %d" %(i, int(m - j)))
            break
        if (int(m + j) in b):
            print("%d %d" %(i, int(m + j)))
            break
        j += 1
    break

### FIXED CODE ###

import sys

sys.setrecursionlimit(10000)

def search(a, b, left, right):
    mid = int(left + (right - left) / 2)
    if(b[mid] == a):
        return b[mid]
    if(len(b) <= mid + 1):
        return b[mid]
    if(b[mid] >= a and a >= b[mid+1]):
        if(b[mid]- a >= a - b[mid+1]):
            return b[mid+1]
        else:
            return b[mid]
    if(b[mid] <= a):
        return search(a, b, left, mid)
    else:
        return search(a, b, mid, right)

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

b = sorted(a, reverse=True)
for i in b:
    m = i/2
    j = search(m, b, 0, len(b))
    print("%d %d" %(i, j))
    break
### BUGGY CODE ###


from collections import defaultdict
s = input().split()
n = int(s[0])
s = input().split()
d = defaultdict(int)
for i in s:
    d[i]+=1
keys=list(d.keys())

for i in range(1,n+1):
    if str(i) in keys:
        print(d[str(i)])
    else:
        print(0)


### FIXED CODE ###

s = input().split()
n = int(s[0])
s = input().split()
d = [0]*n
for i in s:
    d[int(i)-1]+=1

for i in range(n):
    print(d[i])
### BUGGY CODE ###

n, k = input().strip().split(' ')
n, k = [int(n),int(k)]
l = []
for i in range(n):
    h = input()
    h = int(h)
    l.append(h)
dl = sorted(l)
ans = float('inf')
for j in range(n-k+1):
    ddl = []
    for a in range(k):
        ddl.append(dl[j+a])
    if max(ddl) - min(ddl) <= ans:
        ans = max(ddl) - min(ddl)
print(int(ans))


### FIXED CODE ###

n, k = input().strip().split(' ')
n, k = [int(n),int(k)]
l = []
for i in range(n):
    h = input()
    h = int(h)
    l.append(h)
dl = sorted(l)
ans = float('inf')
for j in range(n-k+1):
    if abs(dl[j+k-1] - dl[j]) <= ans:
        ans = abs(dl[j+k-1] - dl[j])
print(int(ans))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque()
    q.append((i,j))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] < dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

def main():
    anss = 0
    for i in range(h+2):
        for j in range(w+2):
            if A[i][j] == "#":
                continue
            anss = max(anss,bfs(i,j))
    print(anss)
            
main()
    



### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque()
    q.append((i,j ))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] <= dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

anss = 0
for i in range(h+2):
    for j in range(w+2):
        if A[i][j] == "#":
            continue
        anss = max(anss,bfs(i,j))
print(anss)
### BUGGY CODE ###

x,y,a,b,c = map(int, input().split(" "))
plist= sorted(list(map(int, input().split(" "))),reverse=True)[0:x]
qlist= sorted(list(map(int, input().split(" "))),reverse=True)[0:y]
rlist= list(map(int, input().split(" ")))

plist.extend(qlist)
plist.sort()

rlist.sort(reverse=True)

n = min(len(plist),len(rlist))
results = [sum(plist)]

for i in range(n):
  plist[i]=rlist[i]
  results.append(sum(plist))
  
print(max(results))

### FIXED CODE ###

x,y,a,b,c = map(int, input().split(" "))
plist= sorted(list(map(int, input().split(" "))),reverse=True)[0:x]
qlist= sorted(list(map(int, input().split(" "))),reverse=True)[0:y]
rlist= sorted(list(map(int, input().split(" "))),reverse=True)

plist.extend(qlist)
plist.sort()
n = min(x+y,len(rlist))
i = 0

while i < n and rlist[i]>plist[i]:
  i += 1
if i == 0:
  print(sum(plist))
else:
  print(sum(plist[i:x+y])+sum(rlist[0:i]))
### BUGGY CODE ###

import sys
from collections import deque

def merge(deq, left, mid, right, compare_counter):
    n_fore = mid - left
    n_rear = right - mid
    l_fore = [deq[left + i] for i in range(n_fore)]
    l_fore.append(sys.maxsize)
    #print(left, mid, right)
    l_rear = [deq[mid + i] for i in range(n_rear)]
    l_rear.append(sys.maxsize)
    i = j = 0
    for k in range(left, right):
        compare_counter[0] += 1
        if l_fore[i] < l_rear[j]:
            deq[k] = l_fore[i]
            i += 1
        else:
            deq[k] = l_rear[j]
            j += 1

def merge_sort(deq, left, right, compare_counter):
    compare_times = 0
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(deq, left, mid, compare_counter)
        merge_sort(deq, mid, right, compare_counter)
        merge(deq, left, mid, right, compare_counter)
    return compare_times

def main():
    n = int(input())
    deq = deque()
    [deq.append(int(x)) for x in input().split()]
    compare_counter = [0]
    compare_times = merge_sort(deq, 0, n, compare_counter)
    print(" ".join(map(str, deq)))
    print(compare_counter[0])
    return


main()


### FIXED CODE ###

import sys
#import time

compare_counter = 0
array = [0 for x in range(500000)]

def merge(left, mid, right):
    n_fore = mid - left
    n_rear = right - mid
    l_fore = array[left:left + n_fore]
    l_fore.append(sys.maxsize)
    l_rear = array[mid:mid + n_rear]
    l_rear.append(sys.maxsize)

    #print(left, mid, right)
    i = j = 0
    global compare_counter
    compare_counter += (right - left)
    for k in range(left, right):
        if l_fore[i] < l_rear[j]:
            array[k] = l_fore[i]
            i += 1
        else:
            array[k] = l_rear[j]
            j += 1


def merge_sort(left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)
    return


def main():
    #start = time.time()
    n = int(input())
    for idx, tmp in enumerate(input().split()):
        array[idx] = int(tmp)
    #print("time", time.time()-start)
    merge_sort(0, n)
    #print("time", time.time()-start)
    print(" ".join(map(str, array[:n])))
    print(compare_counter)
    #print("time",time.time()-start)
    return


main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

N,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(N)]

dp=[[-1]*(W+1) for i in range(N+1)]

def calc(n,w):
    if n<0:
        return 0
    if dp[n][w]>=0:
        return dp[n][w]
    cw,cv=wv[n]
    r1,r2=0,0
    r1=calc(n-1,w)
    if (cw+w)<=W:
        r2=calc(n-1,cw+w)+cv

    return max([r1,r2])

print(calc(N-1,0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

N,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(N)]

dp=[[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(0,W+1):
        if (j-wv[i][0])>=0:
            dp[i+1][j] = max([dp[i][j],dp[i][j-wv[i][0]] + wv[i][1]])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = list(input())
L = len(S)

c = 0
t = 0
md = [0] * 2019
md[0] += 1
for i in range(L - 1, -1, -1):
    t += int(S[i]) * pow(10, c)
    c += 1
    md[t % 2019] += 1

ans = 0
for i in range(2019):
    m = md[i]

    if m == 0:
        continue

    ans += m * (m - 1) // 2

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = list(input())
L = len(S)

c = 0
t = 0
md = [0] * 2019
md[0] += 1
for i in range(L - 1, -1, -1):
    t += int(S[i]) * pow(10, c, 2019)
    c += 1
    md[t % 2019] += 1

ans = 0
for i in range(2019):
    m = md[i]

    if m == 0:
        continue

    ans += m * (m - 1) // 2

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

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    A.sort()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1




    def make_divisors(n):
        lower_divisors , upper_divisors = deque(),deque()
        for i in range(1,int(n**0.5)+1):
            if n % i == 0:
                lower_divisors.append(i)
                if i != n // i:
                    upper_divisors.appendleft(n//i)
            i += 1
        upper_divisors
        return lower_divisors + upper_divisors




    F = deque()
    for a in A:
        F.append(make_divisors(a))
    ans = 0
    Not_Divisible = [False] * (max(A)+1)
    for f in F:
        for d in f:
            if Not_Divisible[d]:
                break
        else:
            Not_Divisible[f[-1]] = True
            if count[f[-1]] == 1:
                ans += 1
    print(ans)
    dbg(F)
    dbg(Not_Divisible)
    
main()

### FIXED CODE ###

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1
    A = list(set(A))
    A.sort()

    if count[1] == 1:
        print(1)
        return
    if count[1] > 1:
        print(0)
        return

    sup = max(A)+1
    Not_Divisible = [True] * sup
    Not_Divisible[0] = False


    for a in A:
        if Not_Divisible[a]:
            for i in range(a*2,sup,a):
                Not_Divisible[i] = False

    ans = 0
    for a in A:
        if Not_Divisible[a] and count[a] == 1:
            ans += 1

    print(ans)
            


    
main()
### BUGGY CODE ###

N = int(input()) #get 1st row
inlist = [input() for i in range(N)] #read row (add int using brackets if needed)
result = []

#make dictionary from input parameters
for component in inlist :
    dic = {}
    #read each
    for n in component:
        if n in dic.keys():
            dic[n] += 1
        else :
            dic[n] = 1
    result.append(dic)

counter = 0
for k1, v1 in enumerate(result):
    for k2, v2 in enumerate (result):
        if v1 == v2 and k1 > k2:
            counter += 1

print (counter)

### FIXED CODE ###

N = int(input()) #get 1st row
inlist = [input() for i in range(N)] #read row (add int using brackets if needed)
result = {}

def combination(a):
    x = 1
    x = a * (a-1) / 2
    return x

#make dic from input parameters
for component in inlist :
    dic = []
    for n in component:
        dic.append(n)
    dic.sort()
    dic2 = "".join(dic)
    if dic2 in result.keys():
        result[dic2] += 1
    else :
        result[dic2] = 1

#count the number
counter = 0
for v in result.values():
    counter += combination(v)

print (int(counter))
### BUGGY CODE ###

string = input()
B = int(input())

for i in range(B):
    cmd = input().split()
    if len(cmd) == 1 and cmd[0] == "1":
        string = string[::-1]
    else:
        _, n, c = cmd
        # n = int(n)
        if n == "1":
            string = c + string
        else:
            string = string + c
print(string)

### FIXED CODE ###

from collections import deque

string = input()
x = deque()
for s in string:
    x.append(s)

head_left = True
B = int(input())
for i in range(B):
    cmd = input().split()
    if len(cmd) == 1 and cmd[0] == "1":
        head_left = not head_left
    else:
        _, n, c = cmd
        if (n == "1" and head_left) or (n == "2" and not head_left):
            x.appendleft(c)
        else:
            x.append(c)

if head_left:
    print("".join(list(x)))
else:
    print("".join(reversed(list(x))))
### BUGGY CODE ###

import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X] #最後までの距離
answer = 0
for i in range(1, N):
    answer += (X[i-1] * limit // i)%MOD
    answer %= MOD

print(answer)



### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

MOD = 10 ** 9 + 7
U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N = ir()
X = np.array(lr())

inv = np.zeros(U, np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD
coef = inv[1:N].cumsum() % MOD
answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]
print(answer % MOD)
# 35
### BUGGY CODE ###

# K = 37564
# S = "whydidyoudesertme"
# K = 5
# S = "oof"
K = int(input())
S = input()

P = 10 ** 9 + 7
N = len(S)

P25 = [1] * (K + 1)
P26 = [1] * (K + 1)
F = [1] * (N + K)
INV = [1] * (N + K)
INVF = [1] * (N + K)

p25 = 1
p26 = 1
for i in range(1, K + 1):
    p25 *= 25
    p25 %= P
    P25[i] = p25

    p26 *= 26
    p26 %= P
    P26[i] = p26

f = 1
invf = 1
for i in range(2, N + K):
    f *= i
    f %= P
    F[i] = f

    INV[i] = P - INV[P % i] * (P // i) % P
    invf *= INV[i]
    invf %= P
    INVF[i] = invf


def comb_rep(n, r):
    return (F[n + r - 1] * INVF[r] % P) * INVF[n - 1] % P


ret = 0
for i in range(K + 1):
    ret += (
        P25[i] *
        P26[K - i] % P *
        comb_rep(N, i) % P
    )
print(ret % P)


### FIXED CODE ###

#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys


def main(K, N):
    P = 10 ** 9 + 7

    P25 = [1] * (K + 1)
    P26 = [1] * (K + 1)
    F = [1] * (N + K)
    INV = [1] * (N + K)
    INVF = [1] * (N + K)

    p25 = 1
    p26 = 1
    for i in range(1, K + 1):
        p25 *= 25
        p25 %= P
        P25[i] = p25

        p26 *= 26
        p26 %= P
        P26[i] = p26

    f = 1
    invf = 1
    for i in range(2, N + K):
        f *= i
        f %= P
        F[i] = f
        q, r = divmod(P, i)
        INV[i] = -INV[r] * q % P
        invf *= INV[i]
        invf %= P
        INVF[i] = invf

    def comb_rep(n, r):
        return (F[n + r - 1] * INVF[r] % P) * INVF[n - 1] % P

    ret = 0
    for i in range(K + 1):
        ret += (
            P25[i] *
            P26[K - i] % P *
            comb_rep(N, i) % P
        )
    return (ret % P)


if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8)')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
    exit()
else:
    # read parameter
    from my_module import main
    K = int(input())
    S = input()
    print(main(K, len(S)))
### BUGGY CODE ###

# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	for i,j in q:
		for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
			if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
				grid[r][c] = grid[i][j] + 1
				maxx = max(maxx,grid[r][c])
				q.append([r,c])
	return maxx

H,W = map(int, raw_input().split())
grid = []
for h in range(H):
	s = list(raw_input())
	grid.append(s)
ans = solve(grid)
print(ans)



### FIXED CODE ###

# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, raw_input().split())
grid = []
for h in range(H):
	s = list(raw_input())
	grid.append(s)
ans = solve(grid)
print(ans)
### BUGGY CODE ###

from collections import Counter

def altar(a,b):
    cnt = 0
    for k in range(len(b)):
        while a and a[0][0]<b[k][0]:
           cnt += a.pop(0)[1]
        b[k] = (b[k][0],b[k][1]*cnt)

input()
a,b,c = [sorted(dict(Counter(map(int,input().split()))).items(),key=lambda x:x[0])for _ in "abc"]
altar(a,b)
altar(b,c)
print(sum([x[1] for x in c]))

### FIXED CODE ###

import bisect
n=int(input())
a,b,c = [sorted(map(int,input().split())) for _ in "abc"]
print(sum([bisect.bisect_left(a,x)*(n-bisect.bisect_right(c,x)) for x in b]))
### BUGGY CODE ###

import sys
read = lambda : sys.stdin.readline().rstrip('\n')
tint = lambda x: [int(x) for x in x.split()]
inf = float('inf')

def main():
    #n, k = tint(read())
    #stones = tint(read())
    n, k = map(int, input().split())
    stones = tuple(map(int, input().split()))
    dp = [inf]*n
    dp[0] = 0
    for i in range(n):
        for t in range(1, k+1):
            if i+t < n:
                v = dp[i]+abs(stones[i]-stones[i+t])
                if dp[i+t] > v:
                    dp[i+t] = v
    print(dp[-1])


if __name__ == '__main__':    
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

import numpy as np
import math as mt
N=int(input())
#R=map(int, input().split())
A=list(map(int,input().split()))
count=1
p_count=0
for i in range(0,N-1):
    print(A.count(i+1))
print(0)


### FIXED CODE ###

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

import sys
n = int(sys.stdin.readline())
li = []
for _ in range(n):
  li.append(sys.stdin.readline().strip())
li2 = list(set(li))
li2.sort(reverse = False)
cnt_box = []
for i in li2:
  cnt_box.append(li.count(i))
m = max(cnt_box)
i = 0
while i < len(cnt_box):
  if cnt_box[i] == m:
    print(li2[i])
  i += 1


### FIXED CODE ###

import sys
import math
import itertools
import numpy
import collections

rl = sys.stdin.readline

n = int(rl())

li = []
for _ in range(n):
    li.append(rl().rstrip())
c = collections.Counter(li)
max_cnt = 0
li = []
for k, v in c.items():
    if v < max_cnt:
        continue
    elif v == max_cnt:
        li.append(k)
    else:
        max_cnt = v
        li = [k]
li.sort()
for i in li:
    print(i)
### BUGGY CODE ###

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

mo=10**9+7
an=0
for i in range(n-1):
    for j in range(i+1,n):
        an+=(a[i]%mo)*(a[j]%mo)
        an%=mo
print(an)

### FIXED CODE ###

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

mo=10**9+7
an=0
wk=0
ru=[]
for i in a:
    wk+= i
    ru.append(wk%mo)
for i in range(n-1):
    an+=a[i]*(ru[n-1]-ru[i])
    an%=mo

print(an)