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

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

num = 2**(n-1).bit_length()
def segfunc(x, y): return max(x, y)
seg = [0]*(2*num-1)
for i in range(n):
  seg[i+num-1] = a[i]
for i in range(num-2, -1, -1):
  seg[i] = segfunc(seg[2*i+1], seg[2*i+2])
def update(i, x):
  i += num-1
  seg[i] = x
  while i:
    i = (i-1)//2
    seg[i] = segfunc(seg[i*2+1], seg[i*2+2])
def query(l, r):
  l += num-1
  r += num-2
  if l == r:
    return seg[l]
  s = seg[l]
  l += 1
  while r-l > 1:
    if ~l % 2:
      s = segfunc(seg[l], s)
    if r % 2:
      s = segfunc(seg[r], s)
      r -= 1
    l //= 2
    r = (r-1)//2
  if l == r:
    return segfunc(s, seg[l])
  return segfunc(s, segfunc(seg[l], seg[r]))

for _ in range(q):
  t,a,b=map(int,input().split())
  if t==1:
    update(a-1,b)
  if t==2:
    print(query(a-1,b))
  if t==3:
    ng=a-1
    ok=n+1
    while ng+1!=ok:
      mid=(ng+ok)//2
      if query(ng,mid)>=b:ok=mid
      else:ng=mid
    print(ok)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

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

num = 2**(n-1).bit_length()
def segfunc(x, y): return max(x, y)
seg = [0]*(2*num-1)
for i in range(n):
  seg[i+num-1] = a[i]
for i in range(num-2, -1, -1):
  seg[i] = segfunc(seg[2*i+1], seg[2*i+2])
def update(i, x):
  i += num-1
  seg[i] = x
  while i:
    i = (i-1)//2
    seg[i] = segfunc(seg[i*2+1], seg[i*2+2])
def query(l, r):
  l += num-1
  r += num-2
  if l == r:
    return seg[l]
  s = seg[l]
  l += 1
  while r-l > 1:
    if ~l % 2:
      s = segfunc(seg[l], s)
    if r % 2:
      s = segfunc(seg[r], s)
      r -= 1
    l //= 2
    r = (r-1)//2
  if l == r:
    return segfunc(s, seg[l])
  return segfunc(s, segfunc(seg[l], seg[r]))

for _ in range(q):
  t,a,b=map(int,input().split())
  if t==1:
    update(a-1,b)
  if t==2:
    print(query(a-1,b))
  if t==3:
    ng=a-1
    ok=n+1
    while ng+1!=ok:
      mid=(ng+ok)//2
      if query(ng,mid)>=b:ok=mid
      else:ng=mid
    print(ok)
### BUGGY CODE ###

N,M = map(int,input().split())

listA=[] #appendのために宣言が必要
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
        #または、quit(),os.exit()をして止める。

#print(listA)
#[[1, 2, 2, 3, 1], [4, 5, 3, 4, 1, 2, 3, 4], [2, 3, 5, 6, 0, 2]]
    
count = 0
for i in range(1,N+1):
  count1 = 0
  for j in range(M):
    if  i < listA[j][0] or listA[j][1] < i:
      break;
    if j == M-1:
      count += 1
print(count)

### FIXED CODE ###

N,M = map(int,input().split())

listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
L=[]
R=[]
for i in listA:
  L.append(i[0])
  R.append(i[1])
maxL = max(L)
minR = min(R)

count = 0
for i in range(1,N+1):
  if maxL <= i <= minR:
    count+=1
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans =1;
iszero = False

if 0 in A:
  iszero = True

for i in range(N):
  if(iszero):
    ans = 0
    break
    
  ans *= A[i]
  
  if(ans>10**18):
    ans = -1

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans =1;
iszero = False

if 0 in A:
  iszero = True
for i in range(N):
  if(iszero):
    ans = 0
    break
  ans *= A[i] 
  if ans>10**18:
    ans = -1
    break

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

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N,K,Q=map(int,input().split())

A=[int(input()) for _ in range(Q)]
S=[K]*N

for i in range(Q):
	S[A[i]-1]+=1
	for j in range(N):
		S[j]-=1
		if S[j]<=0:
			S[j]=-10000000000
		
for k in range(N):
	if S[k]>0:
		print("Yes")
	else:
		print("No")
	

### FIXED CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N,K,Q=map(int,input().split())

A=[int(input()) for _ in range(Q)]
S=[K-Q]*N


for i in range(Q):
	S[A[i]-1]+=1	
	
for k in range(N):
	if S[k]>0:
		print("Yes")
	else:
		print("No")
### BUGGY CODE ###

from math import gcd
K = int(input())
sumval = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            g = gcd(gcd(a,b),c)
            sumval += g
print(sumval)

### FIXED CODE ###

import math
K = int(input())
sumval = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        f = math.gcd(a,b)
        for c in range(1, K+1):
            g = math.gcd(f,c)
            sumval += g
print(sumval)
### BUGGY CODE ###

direction = input()

def next(direction, current):
	output = [0] * len(current)

	for i in range(len(direction)):
		if direction[i] == 'R':
			output[i+1] += current[i]
		if direction[i] == 'L':
			output[i-1] += current[i]

	return output

def solve(direction):
	original = [1] * len(direction)

	prev2 = next(direction, original)
	prev1 = next(direction, prev2)

	count = 2
	while True:
		next_state = next(direction, prev1)
		count += 1
		if next_state == prev2:
			if count % 2 == 0:
				print(' '.join(map(str, prev2)))
				return
			else:
				print(' '.join(map(str, prev1)))
				return
		prev2 = prev1
		prev1 = next_state

solve(direction)

# print(solve('RRLRL'))
# print(solve('RRLLLLRLRRLL'))

### FIXED CODE ###

direction = input()

def next(direction, current):
	output = [0] * len(current)

	for i in range(len(direction)):
		if direction[i] == 'R':
			output[i+1] += current[i]
		if direction[i] == 'L':
			output[i-1] += current[i]

	return output

def s(inp):
	r = len([x for x in inp if x == 'R'])
	l = len([x for x in inp if x == 'L'])

	R = L = 0
	for i in range(0, r, 2):
		R += 1
	for i in range(1, r, 2):
		L += 1
	for i in range(0, l, 2):
		L += 1
	for i in range(1, l, 2):
		R += 1
	
	output = [0 for _ in range(len(inp))]
	output[r-1] = R
	output[r] = L
	return output

def solve(inp):
	r = len([x for x in inp if x == 'R'])
	l = len([x for x in inp if x == 'L'])

	output = [0] * len(inp)
	if r == l:
		output[r-1] = output[r] = r
	else:
		m = max(l-1, r-1)
		if m % 2 == 1:
			output[r-1] = r
			output[r] = l
		else:
			output[r-1] = l
			output[r] = r
		


def solve(direction, start, end, output):
	original = [1] * (end-start)

	sub_direction = direction[start:end]

	prev2 = next(sub_direction, original)
	prev1 = next(sub_direction, prev2)

	count = 2

	output.append(s(direction[start:end]))

	# while True:
	# 	next_state = next(sub_direction, prev1)
	# 	count += 1
	# 	if next_state == prev2:
	# 		if count % 2 == 0:
	# 			output.append(prev2)
	# 			# print(' '.join(map(str, prev2)))
	# 			return
	# 		else:
	# 			output.append(prev1)
	# 			# print(' '.join(map(str, prev1)))
	# 			return
	# 	prev2 = prev1
	# 	prev1 = next_state

# direction = 'RRRLLRLLRRRLLLLL'
parts = []
prev = 0
for i in range(len(direction)-1):
	if direction[i] == 'L' and direction[i+1] == 'R':
		parts.append((prev,i+1))
		prev = i+1

parts.append((prev,len(direction)))

# print(parts)
output = []
for start,end in parts:
	solve(direction, start, end, output)

# print(output)
final = [x for  y in output for x in y]
print(' '.join(map(str, final)))


# print(solve('RRLRL'))
# print(solve('RRLLLLRLRRLL'))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
count = 0
for i in range(N):
    temp=0
    for j in range(i,N):
        if temp & A[j] == 0:
            temp = temp + A[j]
            count = count + 1
        else:
            break;
            
print(count)    

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
count = 0
prev_lastidx=-1
initial=0
for i in range(N):
    temp=initial
    for j in range(prev_lastidx+1,N):
        if temp & A[j] == 0:
            temp = temp + A[j]
            prev_lastidx = j
        else:
            prev_lastidx = j-1
            initial = temp - A[i]
            break;
    count = count + (prev_lastidx - i + 1)
print(count)
### BUGGY CODE ###

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

t = list(map(int,input().split()))

for _ in range(m):
    a, b = (int(x) for x in input().split())
    for _ in range(a):
        t.append(b)
t.sort(reverse=True)

res = 0

for i in range(n):
    res += t[i]
print(res)

### FIXED CODE ###

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

t = list(map(int,input().split()))
ab=[]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a,b])

t.sort(reverse=True)
ab = sorted(ab, key=lambda x: -x[1])
count = 0
for i,j in ab:
    t += [j]*i
    count += i
    if n <= count:
        break

t.sort(reverse=True)
        
print(sum(t[:n]))
### BUGGY CODE ###

n=int(input())
l=[]
t=int(n**0.5)
while len(l)==0:
    if n%t==0:
        l.append((t,n//t))
    t+=1
x,y=l[0][0],l[0][1]
ans=max(len(list(str(x))),len(list(str(y))))
print(ans)

### FIXED CODE ###

n=int(input())
l=[]
t=int(n**0.5)
while len(l)==0:
    if n%t==0:
        l.append((t,n//t))
    t-=1
x,y=l[0][0],l[0][1]
ans=max(len(list(str(x))),len(list(str(y))))
print(ans)
### BUGGY CODE ###

# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

import sys
readline = sys.stdin.readline

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] # 試合グラフ
indegree = [0 for i in range((N * (N - 1)) // 2)] # 入次数
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    # i と a - 1の試合
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 # 試合に対する入次数が1
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] # 試合完了
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)
# この頂点からスタートしてBFSで、同じ頂点は通らないようにして移動
# 行けない場所があったら閉路あり
if len(stack) == 0:
  print(-1)
  exit(0)
  
from collections import deque
q = deque(stack)
visited = set()
while q:
  v = q.popleft()
  if v in visited:
    continue
  visited.add(v)
  for child in G[v]:
    q.append(child)

if len(visited) != (N * (N - 1)) // 2:
  print(-1)
  exit(0)

# stackに入った頂点からスタートしてグラフの最長経路を求める
# 閉路なしなので、より長い道があれば更新

stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append([i,1])

dist = [0 for i in range((N * (N - 1)) // 2)]
while stack:
  v, d = stack.pop()
  if dist[v] >= d:
    continue
  dist[v] = d
  for child in G[v]:
    stack.append([child, d + 1])
  
print(max(dist))

### FIXED CODE ###

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

def actual(N, A):
    count = 0

    while True:
        is_all_even = all([a % 2 == 0 for a in A])

        if is_all_even:
            A = [a // 2 for a in A]
            count += 1
        else:
            break

    return count

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

print(actual(N, A))

### FIXED CODE ###

def actual(N, A):
    count = 0
    while True:
        is_all_even = all([a % 2 == 0 for a in A])

        if is_all_even:
            A = [a // 2 for a in A]
            count += 1
        else:
            return count

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

print(actual(N, A))
### BUGGY CODE ###

N, K = map(int,input().split())
H = list(map(int,input().split()))
DP = [0]*(N+1)
for i in range(2,N+1):
  Hi = H[i-1]
  DP[i] = min( [DP[j] + abs(Hi - H[j-1]) for j in range(max(1,i-K),i)])
print(DP[-1])

### FIXED CODE ###

N, K = map(int,input().split())
H = list(map(int,input().split()))
import numpy as np
dp = np.zeros(N,dtype=np.int)
harr = np.array(H)
for i in range(1,N):
  St = max(0,i-K)
  Hi = harr[i]
  dp[i] = min(dp[max(0,i-K):i] + np.abs(Hi - harr[max(0,i-K):i]))
print(dp[-1])
### BUGGY CODE ###

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

for k in range(N):
	for i in range(N):
		for j in range(N):
			if d[i][j] > d[i][k] + d[k][j]:
				d[i][j] = d[i][k] + d[k][j]
				d[j][i] = d[i][k] + d[k][j]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

print(ans)

### FIXED CODE ###

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

for k in range(N):
	for i in range(N):
		for j in range(N):
			if d[i][j] > d[i][k] + d[k][j]:
				d[i][j] = d[i][k] + d[k][j]
				d[j][i] = d[i][k] + d[k][j]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

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

import math
import sys
import itertools
import queue
from fractions import gcd

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

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    s = list(sys.stdin.readlines())
    # new_s=sorted(s)
    char_list=[]
    for i in s:
        i = i.replace('\n','')
        new_s=sorted(i)
        new_s = ''.join(new_s)
        char_list.append(new_s)


    c = 0
    for j in range(n):
        if char_list[j] in char_list[j+1:]:
            c+=char_list[j+1:].count(char_list[j])
    print(c)

### FIXED CODE ###

import math
import sys
import itertools
import queue
from fractions import gcd

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

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    s = list(sys.stdin.readlines())
    new_s=sorted(s)
    char_list=[]
    dic ={}
    for i in s:
        i = i.replace('\n','')
        new_s=sorted(i)
        new_s = ''.join(new_s)
        char_list.append(new_s)
        if new_s not in dic:
            dic[new_s] = 1
        else:
            dic[new_s] += 1
    # c = 0
    # for j in range(n):
    #     if char_list[j] in char_list[j+1:]:
    #         c+=char_list[j+1:].count(char_list[j])
    # print(c)

    def combinations_count(n, r):
        if n - r < 0:
            return 0
        else:
            return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    # print(char_list)
    # print(dic)
    c=0
    # print(dic.values())
    for i in dic.values():
        c+=combinations_count(i, 2)
    print(c)
### BUGGY CODE ###

data = []
res = []
i = int(input())

for _n in range(i):
	data.append(int(input()))

for n in range(i):
	res.append(max(data[0:n]+data[n+1:]))

for item in res:
	print(item)



### FIXED CODE ###

import copy

data = []
i = int(input())

data = [int(input()) for _n in range(i)]
maxInt = max(data)
data2 = copy.copy(data)
data2.remove(maxInt)
max2Int = max(data2)
for n in range(i):
	if maxInt != data[n]:
		print(maxInt)
	else:
		print(max2Int)
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 998244353
list_s = []
for _ in range(k):
    l, r = map(int, input().split())
    list_s.append((l, r))
dp = [0] * (n + 1)
sdp = [0] * (n + 1)
dp[1] = 1
sdp[0] = 0
sdp[1] = 1

for i in range(2, n + 1):
    for l, r in list_s:
        dl = max(0, i - r - 1)
        dr = max(0, i - l)
        dp[i] += sdp[dr] - sdp[dl]
        sdp[i] = sdp[i - 1] + dp[i]
print(dp[n] % mod)

### FIXED CODE ###

n, k = map(int, input().split())
mod = 998244353
list_s = []
for _ in range(k):
    l, r = map(int, input().split())
    list_s.append((l, r))
dp = [0] * (n + 1)
sdp = [0] * (n + 1)
dp[1] = 1
sdp[0] = 0
sdp[1] = 1

for i in range(2, n + 1):
    for l, r in list_s:
        dl = max(0, i - r - 1)
        dr = max(0, i - l)
        dp[i] += sdp[dr] - sdp[dl]
        sdp[i] = (sdp[i - 1] + dp[i]) % mod
print(dp[n] % mod)
### BUGGY CODE ###

R,G,B,N=(int(x) for x in input().split())
cnt=0
for r in range((N//R)+1):
    for g in range(((N-R*r)//G)+1):
        if (N-R*r-G*g)<0: continue
        if (N-R*r-G*g)%B==0:
            cnt=cnt+1
print (cnt)

### FIXED CODE ###

R,G,B,N=list(map(int,input().split()))
cnt=0
for r in range((N//R)+1):
    for g in range(((N-R*r)//G)+1):
        if (N-R*r-G*g)%B==0:
            cnt=cnt+1
print (cnt)
### BUGGY CODE ###

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

brr = []
prod = 1
for i in range(k):
    prod*=arr[i]

for i in range(k,n):
    prev = prod
    prod = prod//arr[i-k]*arr[i]
    if prod>prev:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range(k,n):
    if arr[i-k]<arr[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def button(t):
    for k in range(t+1):
        a[k] += 1
    return a

n = int(input())
a = [0]*n
b = [0]*n

for i in range(n):
    a[i],b[i] = map(int,input().split())

count = 0
for i in range(n):
    while True:
        if a[n-1-i] % b[n-1-i] == 0:
            break
        else:
            button(n-1-i)
            count += 1

print(count)

### FIXED CODE ###

n = int(input())
a = [0]*n
b = [0]*n

for i in range(n):
    a[i],b[i] = map(int,input().split())
a.reverse()
b.reverse()
count = 0
for i in range(n):
    if (a[i]+count)%b[i] == 0:
        pass
    elif a[i]+count > b[i]:
        count += (b[i]*(((a[i]+count)//b[i])+1))-(a[i]+count)
    else:
        count += b[i] - (a[i]+count)
print(count)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
out = []
for i in range(n):
    out.append(str(a.index(n-i)+1))
print(' '.join(list(reversed(out))))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
out = [0] * n
for i in range(len(a)): out[a[i] - 1] = i + 1
print(' '.join([str(i) for i in out]))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
cost = [[i - j if i > j else j - i for i in h] for j in h]
#dp[i] をiまでの最小コスト
INF = 10**9
dp = [INF for i in range(N)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i + k >= N:
            break
        mini = dp[i] + cost[i][i+k]
        if dp[i + k] > mini:
            dp[i + k] = mini # i => i+k でのコストの更新
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
#dp[i] をiまでの最小コスト
INF = 10**9
# h.extend([INF for i in range(100)])
dp = [INF for i in range(N)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i + k >= N:
            break
        dp[i + k] = min(dp[i + k], dp[i] + abs(h[i+k] - h[i])) # i => i+k でのコストの更新
print(dp[N-1])
### BUGGY CODE ###

import numpy as np

def factorial(i):
    ans = 1
    for j in range(1,i+1):
        ans *= j
    return ans
N = int(input())
A = [input() for i in range(N)]
a = []
for i in A:
    b = list(i)
    b.sort()
    a.append(b)

a.sort()
c = list(map(list, set(map(tuple, a))))
count = 0
for i in c:
    if a.count(i)==1:
        continue
    if a.count(i) > 2:
        count += factorial(a.count(i)) // (factorial(a.count(i) - 2) * factorial(2))
    else:
        count += 1

print(count)

### FIXED CODE ###

N = int(input())
A=[]
S={}
for i in range(N):
    a = list(input())
    a.sort()
    b = ''.join(a)
    if b not in S:
        S[b] = 1
    else:
        S[b] += 1


count=0
for i in S.values():
    if i==1:
        continue
    count += i*(i-1)//2
print(count)
### BUGGY CODE ###

import sys
from collections import defaultdict
from bisect import insort

n, m = map(int, input().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    if a <= m:
        d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    sub = d[i]
    if len(sub) > 0:
        for j in range(len(sub)):
            insort(resList, sub[j])
    if len(resList) > 0:
        res += resList.pop()

print(res)


### FIXED CODE ###

import sys
from heapq import heappush,heappop

n, m = map(int, sys.stdin.readline().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a <= m:
        d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    if len(d[i]) > 0:
        for j in d[i]:
            heappush(resList, -j)
    if len(resList) > 0:
        res += (-1) * resList[0]
        heappop(resList)

print(res)
### BUGGY CODE ###

n = input()
line = input()
n = int(n)
a_list = line.split(" ")
a_list = [int(a) for a in a_list]

set_list = list(set(a_list))

if n-1 == len(set_list):
    for i in range(n):
        if i == n-1:
            print(0)
        else:
            print(1)
else:
    for i in range(n):
        if i+1 in set_list:
            print(a_list.count(i+1))
        else:
            print("0")

### FIXED CODE ###

n = input()
line = input()
n = int(n)
a_list = line.split(" ")
a_list = [int(a) for a in a_list]

ans_list = [0 for i in range(n)]

for a in a_list:
    ans_list[a-1] = ans_list[a-1] + 1

for ans in ans_list:
    print(ans)
### BUGGY CODE ###

import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]

for _ in range(min(k,500)):
    new_a = np.zeros(n, dtype='int64')
    for j,l in enumerate(a):
        for i in range(-l,l+1):
            if j+i >= 0 and j+i<n:
                new_a[j+i]+=1
    a = new_a

print(" ".join([str(x) for x in a]))

### FIXED CODE ###

import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]


for _ in range(k):
    new_a = np.zeros(n+1,dtype=int)
    np.add.at(new_a, np.maximum(0,np.arange(0, n)-a), 1)
    np.add.at(new_a, np.minimum(n,np.arange(0, n)+a+1), -1)
    a = new_a.cumsum()[:-1]
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))