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

from collections import *
from heapq import *
import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def main():
    ans=mint(0)
    n=II()
    aa=LI()
    for i in range(61):
        cnt1=0
        for a in aa:cnt1+=a>>i&1
        ans+=(1<<i)*cnt1*(n-cnt1)
    print(ans)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n = int(input())
    aa = LI()
    cnt = [[0] * 2 for _ in range(61)]
    for a in aa:
        for i in range(61):
            cnt[i][a & 1] += 1
            a >>= 1
    #print(cnt)
    base = 1
    ans = 0
    for c0, c1 in cnt:
        ans += base * c0 * c1
        ans %= md
        base = base * 2 % md
    print(ans)

main()
### BUGGY CODE ###

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

ans = 1

for a in A:
    ans *= a

if ans > 10**(18):
    ans = -1

print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in A:
    print(0)
    exit()

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

    if ans > 10**18:
        ans = -1
        break

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

N=int(input())
S=input()
ans=0
minus=0
for i in range(len(S)-2):
  temp=['']*2
  temp[0]=S[i]
  for j in range(i+1,len(S)-1):
    if S[i]!=S[j]:
      temp[1]=S[j]
    else:
      continue
    if 'R' not in temp:
      ans +=S[j+1:].count('R')
      check_index=i+(j-i)*2
      if check_index<=N-1 and S[check_index]=='R':
        minus+=1
    if 'G' not in temp:
      ans +=S[j+1:].count('G')
      check_index=i+(j-i)*2
      if check_index<=N-1 and S[check_index]=='G':
        minus+=1
    if 'B' not in temp:
      ans +=S[j+1:].count('B')
      check_index=i+(j-i)*2
      if check_index<=N-1 and S[check_index]=='B':
        minus+=1
    continue

print(ans-minus)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from numba import njit

MOD = 10**9 + 7

N = int(readline())
S = np.array(list(read().rstrip()), np.int8)

R = np.sum(S == ord('R'))
B = np.sum(S == ord('B'))
G = np.sum(S == ord('G'))
 
@njit
def f(S):
    N = len(S)
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
          k = j + j - i
          if k >= N:
            break
          if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ret += 1
    return ret
  
answer = R * B * G - f(S)
print(answer)
### BUGGY CODE ###

import sys
from heapq import heapify,heappop,heappush,heapreplace

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  n,m,*lrd=map(int,read().split())
  hp=[]
  for l,r,d in zip(*[iter(lrd)]*3):
    if l>r:
      hp.append((r,l,-d))
    else:
      hp.append((l,r,d))
  heapify(hp)
  if not hp:
    print('Yes')
    return
  while hp:
    ce=heappop(hp)
    while hp:
      ne=hp[0]
      if ce[0]==ne[0]:
        if ce[1]==ne[1]:
          if ce[2]!=ne[2]:
            print('No')
            return
          else:
            heappop(hp)
        else:
          heapreplace(hp,(ce[1],ne[1],ne[2]-ce[2]))
      else:
        break      
  print('Yes')

if __name__=='__main__':
  main()
      
    
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
        return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
# print(n)
# print(s)
s = list(map(list, s))
# print(s)
for i in range(n):
    s[i].sort()
# print(s)
count = 0
for i in range(n):
    a = s[i]
    for j in range(i+1,n):
        b = s[j]
        if a == b:
            count += 1
print(count)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
# print(n)
# print(s)
s = list(map(list, s))
# print(s)
for i in range(n):
    s[i].sort()
    s[i] = "".join(s[i])
# print(s)
dic = {}
for i in range(n):
    if s[i] in dic:
        dic[s[i]] += 1
    else:
        dic.setdefault(s[i],1)
a = list(dic.values())
# print(a)
import math
count = 0
for i in range(len(a)):
    if a[i] >= 2:
        count += math.factorial(a[i])//(math.factorial(a[i]-2)*2)
print(count)
### BUGGY CODE ###

MOD = 10**9+7
S = input()
l = len(S)
dp = [[0] * 13 for _ in range(l+1)]
dp[0][0] = 1
p = 1
for i in range(l):
  if(S[i] != '?'):
    n = int(S[i])
    for j in range(13):
      dp[i+1][(j*10+n)%13] += dp[i][j]
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][(j*10+k)%13] += dp[i][j]
  for j in range(13):
    dp[i+1][j] = dp[i+1][j]%MOD
  p = (p*10)%MOD    
print(dp[l][5])

### FIXED CODE ###

MOD = 10**9+7
S = input()
l = len(S)
dp = [[0] * 13 for _ in range(l+1)]
dp[0][0] = 1
p = 1
for i in range(l):
  if(S[i] != '?'):
    n = int(S[i])
    for j in range(13):
      dp[i+1][(j*10+n)%13] += dp[i][j]
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][(j*10+k)%13] += dp[i][j]
  for j in range(13):
    dp[i+1][j] = dp[i+1][j]%MOD
  p = (p*10)%MOD    
print(dp[l][5])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(s: str, t: str):
    ls=len(s)
    lt=len(t)
    dp=[[0]*(lt+1) for _ in range(ls+1)] # dp[0:ls+1][0:lt+1]

    for i in range(ls):
        for j in range(lt):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+1
            if dp[i+1][j]>dp[i+1][j+1]: dp[i+1][j+1]=dp[i+1][j]
            if dp[i][j+1]>dp[i+1][j+1]: dp[i+1][j+1]=dp[i][j+1]

    ans=""
    la=dp[ls][lt]
    ttag=lt
    for i in reversed(range(ls+1)):
        if dp[i][ttag]<la:
            ans=s[i]+ans
            la-=1
            ttag-=1

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def solve(s: str, t: str):
    ls=len(s)
    lt=len(t)
    dp=[[0]*(lt+1) for _ in range(ls+1)] # dp[0:ls+1][0:lt+1]

    for i in range(ls):
        for j in range(lt):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+1
            if dp[i+1][j]>dp[i+1][j+1]: dp[i+1][j+1]=dp[i+1][j]
            if dp[i][j+1]>dp[i+1][j+1]: dp[i+1][j+1]=dp[i][j+1]

    ans=""
    while ls>0 and lt>0:
        if dp[ls][lt]==dp[ls-1][lt]:
            ls-=1
        elif dp[ls][lt]==dp[ls][lt-1]:
            lt-=1
        else:
            ans=s[ls-1]+ans
            ls-=1
            lt-=1

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

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

import numpy as np
n,c = map(int,raw_input().split())

imos = [[0 for i in range(10**5+1)] for j in range(c)]


for i in range(n):
	s,t,chan = map(int,raw_input().split())

	imos[chan-1][s-1] += 1
	imos[chan-1][t] -= 1


ans = 0

imoscumsum = []
for i in range(c):
	imoscumsum.append(np.cumsum(imos[i]))

#for i in range(c):
#	print imoscumsum[i]

for i in range(10**5+1):
	count = 0
	for j in range(c):
		if imoscumsum[j][i] != 0:
			count += 1

	ans = max(ans,count)

print ans


### FIXED CODE ###

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

r = [[0 for i in range(c)] for j in range(100000)] 
for dummy in range(n): 
    s, t, c = map(int, input().split())
    for j in range(s - 1, t):
        r[j][c - 1] = 1 

ans = 0
for i in range(100000):
    if sum(r[i]) > ans:
        ans = sum(r[i]) 

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

import sys
sys.setrecursionlimit(4100000)
import math

def gcd(a, b):
    if (a < b) :
        tmp = a
        a = b
        b = tmp
        
    r = a % b
    while (r != 0) :
        a = b
        b = r
        r = a % b
    return int(b)

def lcm(a,b):
    temp = gcd(a,b)
    return int(temp * (a//temp) * (b//temp))




N = int(input())

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



koubai = int(1)
for i in range(N):
    koubai = int(lcm(koubai, A[i]))

ans = int(0)
for i in range(N):
    ans += int(koubai // int(A[i]))
    
ans %= int(1000000007)

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math




N = int(input())


import fractions
a = list(map(int, input().split()))
koubai = a[0]
small = []
for i in range(0, N//2):
    small.append(a[2*i + 1] * a[2*i] // fractions.gcd(a[2*i + 1], a[2*i]))

small.append(a[-1])
for i in range(len(small)):
    koubai = koubai * small[i] // fractions.gcd(koubai, small[i])


ans = int(0)
for i in range(N):
    ans += koubai // a[i]
    
ans %= 1000000007

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

#K : XYZそれぞれは、0以上K以下
#S : X+Y+Zの合計値を示すS

K,S = map(int,input().split())

X=Y=Z=0
result = 0
while(X<=K):
    while(Y<=K):
        while(Z<=K):
            # print("X,Y,Z",X,Y,Z)
            if X+Y+Z<S:
                pass
            elif X+Y+Z==S:
                result +=1
            else:
                break
            Z+=1
        Z=0
        Y+=1
        if X+Y+Z>S:
            break
    Y=0
    X+=1
print(result)

### FIXED CODE ###

#K : XYZそれぞれは、0以上K以下
#S : X+Y+Zの合計値を示すS

K,S = map(int,input().split())

X=Y=Z=0
result = 0
for x in range(K+1):
    for y in range ( K+1 ):
        if 0 <= S-X-Y <=K:
            result +=1
        # Z = S-X-Y
        # # print("XYZ",X,Y,Z)
        # if X+Y+Z == S:
        #     if  Z<=K :
        #         result+=1 
        Y+=1
    Y=0
    X+=1

print(result)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
rain_sum = sum(A) // 2
for i in range(N):
    rain_other = 0
    for j in range((N - 1) // 2):
        rain_other += A[(i + 1 + 2 * j) % N]
    print((rain_sum - rain_other) * 2, end = ' ')


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
rain_sum = sum(A) // 2
rain_other = 0
for i in range((N - 1) // 2):
    rain_other += A[(2 * i + 1) % N]
rain_before = (rain_sum - rain_other) * 2
print(rain_before, end = ' ')
for i in range(N - 1):
    rain_before = 2 * A[i] - rain_before
    print(rain_before, end = ' ')
### BUGGY CODE ###

N = int(input())
an = list(map(int, input().split()))
sum = 0
for k in range(len(an) - 1):
    i = k
    for i in range(len(an) - k - 1):
        sum += (an[k] * an[k + i + 1])
    sum %= (10 ** 9 + 7)
print(sum)

### FIXED CODE ###

p = (10 ** 9 + 7) * 2
N = int(input())
A = [int(x) for x in input().split()]
A2 = [(x ** 2) % p for x in A]
result = (((sum(A) % p) ** 2 - sum(A2) % p) % p) / 2
print(int(result))
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    c = 0
    if A == sorted(A):
        print("Yes")
        c += 1
    else:
        for i, a in enumerate(A):
            A[i] = a-1
            if A == sorted(A):
                print("Yes")
                c += 1
                break
    if c == 0:
        print("No")


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    h = list(map(int, input().split()))
    for i in range(n-1):
        if h[i] < h[i+1]:
            h[i+1] -= 1
        elif h[i] > h[i+1]:
            print('No')
            exit()

    print('Yes')


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

N = int(input())
S = list(int(i) for i in input().split())  
list = []
count = 0

for i in range(N):
    if S[i] not in list:
        num = S[i:].count(S[i])
        if num < S[i]:
            count += num
        elif num > S[i]:
            count += (num-S[i])
    list.append(S[i])

print(count)

### FIXED CODE ###

N = int(input())
S = list(int(i) for i in input().split())  
dict = {}
count = 0

for i in range(N):
    if S[i] not in dict:
        dict[S[i]] = 1
    else:
        dict[S[i]] += 1

for key, value in dict.items():
    if key < value:
        count += (value-key)
    elif key > value:
        count += value

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

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0 for _ in range(n + 1)]
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    ans = [0] * (n + 1)
    visited = []

    def dfs(root, point):
        point += counter[root]
        ans[root] = point
        visited.append(root)
        for j in tree[root]:
            if j in visited:
                continue
            dfs(j, point)
        return

    dfs(1, 0)
    for i in range(1, n + 1):
        print(ans[i], '', end='')
    return ans


m()


### FIXED CODE ###

import queue
import sys
def input(): return sys.stdin.readline().rstrip()

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0] * (n + 1)
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    que = queue.Queue()
    visited = [False] * (n+1)

    def bfs(root, base):
        base += counter[root]
        visited[root] = True
        for e in tree[root]:
            if visited[e]:
                continue
            que.put(e)
            counter[e] += base

        while not que.empty():
            x = que.get()
            point = counter[x]
            visited[x] = True
            for e in tree[x]:
                if visited[e]:
                    continue
                que.put(e)
                counter[e] += point

    bfs(1, 0)
    print(*counter[1:])
    return


m()
### BUGGY CODE ###

import math

n=int(input())

minimum=n-1
for i in range(1,n):
    if(n%i==0):
        minimum=min(minimum,(n//i-1)+(i-1))

print(minimum)


### FIXED CODE ###

import math

n=int(input())
n2=int(math.sqrt(n))

minimum=n-1
for i in range(1,n2+1):
    if(n%i==0):
        minimum=min(minimum,(n//i-1)+(i-1))

print(minimum)
### BUGGY CODE ###

#abc_155_d
#versions of not using numpy
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
#a = np.array(a)
a.sort()

left = -10**18
right = 10**18

while left+1 < right:
    mid = (left+right)//2
    cnt = 0
    
    #run about each element as the first choice
    for i in range(n):
        #count possible pairs that satisfies the condition      
        if(a[i] >= 0):
            #hold the sorted order
            l = -1 
            r = n
            while l+1<r:
                m = (l+r)//2
                if(a[i]*a[m] <= mid):
                    l = m
                else:
                    r = m
            
            cnt += l+1
        
        if(a[i] < 0):
            #reverse the sorted order
            l = -1 
            r = n
            while l+1<r:
                m = (l+r)//2
                if(a[i]*a[m] <= mid):
                    r = m
                else:
                    l = m
                    
            cnt += n - r
        
        if(a[i]**2 <= mid):
            cnt -= 1
        
    cnt /= 2
        
            
    
    """
    if mid >=0:
        cnt += len(zero) * n
    
    cnt += a.searchsorted(mid//plus, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//minus), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt /= 2
    """
    
    if cnt >= k:
        right = mid
    if cnt < k:
        left=mid
   
        
print(right)

### FIXED CODE ###

#abc_155_d
import numpy as np
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = np.array(a)
a.sort()

plus = a[a>0]
zero = a[a==0]
minus= a[a<0]

left = -10**18
right = 10**18

while left+1 < right:
    mid = (left+right)//2
    cnt = 0
    
    if mid >=0:
        cnt += len(zero) * n
    
    cnt += a.searchsorted(mid//plus, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//minus), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt /= 2
    
    if cnt >= k:
        right = mid
    if cnt < k:
        left=mid
        
print(right)
### BUGGY CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n):
    for j in range(1,(n-i)//2+1):
        if i+2*j <= n-1:
            tem = s[i]+s[i+j]+s[i+2*j]
            num_r = tem.count("R")
            num_g = tem.count("G")
            num_b = tem.count("B")
            if num_r == 1 and num_g == 1 and num_b == 1:
                minus += 1
            

print(sum - minus)

### FIXED CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n-2):
    for j in range(2, n-i+1, 2):
        if i+j <= n-1:
            tem = [s[i], s[i+j//2], s[i+j]]
            if tem[0] != tem[1] and tem[0] != tem[2] and tem[1] != tem[2]:
                minus += 1
            

print(sum - minus)
### BUGGY CODE ###

N = int(input())
dic = {}
for i in range(N):
    s = input()
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

for item in sorted(dic.items()):
    if item[1] == max(dic.values()):
        print(item[0])


### FIXED CODE ###

N=int(input())
S=[input() for i in range(N)]
dictionary={}
for word in S:
    if word in dictionary:
        dictionary[word]+=1
    else:
        dictionary[word]=1
maximum=max(dictionary.values())
for key,value in sorted(dictionary.items()):
    if value==maximum:
        print(key)
### BUGGY CODE ###

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

MOD = 998244353

A.sort()
s = 0
for idx, a in enumerate(A):
    s += a
    if s > S:
        break
idx += 1

dp = [[[0] * (idx + 1) for _ in range(S + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1

for i in range(N):
    a = A[i]
    for j in range(S + 1):
        for k in range(idx + 1):
            a = A[i]
            here = dp[i][j][k]
            if j + a <= S and k + 1 <= idx:
                dp[i + 1][j + a][k + 1] += here
            dp[i + 1][j][k] += here

cnt = 0
K = dp[-1][-1]
for i, c in enumerate(K):
    cnt += c * (pow(2, N - i, MOD))
    cnt %= MOD

print(cnt)


### FIXED CODE ###

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

MOD = 998244353

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

for i in range(N):
    ai = A[i]
    for j in range(S + 1):
        here = dp[i][j]
        # aiがTに含まれない
        dp[i + 1][j] += here
        # aiがTに含まれるが, Uに含まれない
        dp[i + 1][j] += here

        dp[i + 1][j] %= MOD

        # aiがUに含まれる
        if j + ai <= S:
            dp[i + 1][j + ai] += dp[i][j]
            dp[i + 1][j + ai] %= MOD

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

from collections import deque

import sys
input = sys.stdin.readline


n = int(input())
a_list = [None for _ in range(n)]
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

for kkk in range(n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit.add(a_list[j].popleft())
                        visit.add(a_list[k].popleft())
                    if num >= n * (n - 1) // 2:
                        break
    if (len(visit) == 0):
        day = -1
        break
    if num >= n * (n - 1) // 2:
        break
print(day)

### FIXED CODE ###

from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    tomorrow = set([])
    if (day == 1):
        player = set([i for i in range(n)])
    for i in player:
        if len(a_list[i]) == 0:
            continue
        j = a_list[i][0]
        if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0) & (i not in tomorrow):
            tomorrow.add(i)
            tomorrow.add(a_list[i][0])
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    player = tomorrow
    if battle_today == 0:
        day = -1
        break
print(day)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [0] * N


for i in range(1, N):
  c = 10 ** 4 * N
  j=0 if i<K else i-K
  for k in range(j, i):
    c1 = dp[k] + abs(h[i]-h[k])
    #print(c1)
    c = min(c1, c)
  dp[i] = c
  #print(dp)
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [0] * N

for i,H in enumerate(h):
  if i != 0:
    j=0 if i<K else i-K
    dp[i] = min(k + abs(l-H) for k,l in zip(dp[j:i], h[j:i]))
print(dp[-1])