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

N, M = 10, 3
ARR = [1, 8, 5, 7, 100, 4, 52, 33, 13, 5]
BRR = [
    [3, 10],
    [4, 30],
    [1, 4]
]

import heapq

N,M = map(int,input().split())
ARR = list(map(int,input().split()))
BRR = []
for i in range(M):
    BRR.append(list(map(int,input().split())))

def calculate(n, m, arr, brr):
    raw = []
    for ar in arr:
        heapq.heappush(raw,ar)
    for br in brr:
        for i in range(br[0]):
            heapq.heappush(raw,br[1])

    while len(raw) > n:
        heapq.heappop(raw)

    print(sum(raw))


calculate(N, M, ARR, BRR)


### FIXED CODE ###

# N, M = 10, 3
# ARR = [1, 8, 5, 7, 100, 4, 52, 33, 13, 5]
# BRR = [
#     [3, 10],
#     [4, 30],
#     [1, 4]
# ]


N,M = map(int,input().split())
ARR = list(map(int,input().split()))
BRR = []
for i in range(M):
    BRR.append(list(map(int,input().split())))

def calculate(n, m, arr, brr):
    raw = []
    for ar in arr:
        raw.append([ar, 1])
    for br in brr:
        raw.append([br[1], br[0]])

    raw = sorted(raw,key=lambda x:-x[0])
    # print(raw)

    offset = 0
    sum = 0
    for ra in raw:
        if offset + ra[1] <= n:
            sum = sum + ra[1] * ra[0]
            offset = offset + ra[1]
        else:
            sum = sum + (n - offset) * ra[0]
            offset = n
            break
    print(sum)

calculate(N, M, ARR, BRR)
### BUGGY CODE ###

H, W = map(int,input().split())
s = []
row = [[None]*W for _ in range(H)]
col = [[None]*W for _ in range(H)]
for _ in range(H):
    s.append(list(input()))
for j in range(H):
    l = s[j]
    for i in range(W):
        if l[i] == "#":
            row[j][i] = 0
        elif i > 0:
            row[j][i] = row[j][i-1] + 1
        else:
            row[j][i] = 1
    for i in range(W-1, -1, -1):
        if l[i] == "#":
            continue
        elif i < W-1:
            row[j][i] = max(row[j][i+1], row[j][i])
for i in range(W):
    for j in range(H):
        if s[j][i] == "#":
            col[j][i] = 0
        elif j > 0:
            col[j][i] = col[j-1][i] + 1
        else:
            col[j][i] = 1
    for j in range(H-1, -1, -1):
        if s[j][i] == "#":
            continue
        elif j < H-1:
            col[j][i] = max(col[j+1][i], col[j][i])
ans = 0
for j in range(H):
    for i in range(W):
        ans = max(row[j][i] + col[j][i] - 1, ans)
print(ans)

### FIXED CODE ###

H, W = map(int,input().split())
s = []
rc = [[[None]*W for _ in range(H)] for _ in range(2)]
for _ in range(H):
    s.append(list(input()))
for j in range(H):
    l = s[j]
    for i in range(W):
        if l[i] == "#":
            rc[0][j][i] = 0
        elif i > 0:
            rc[0][j][i] = rc[0][j][i-1] + 1
        else:
            rc[0][j][i] = 1
    for i in range(W-1, -1, -1):
        if l[i] == "#":
            continue
        elif i < W-1:
            rc[0][j][i] = max(rc[0][j][i+1], rc[0][j][i])
for i in range(W):
    for j in range(H):
        if s[j][i] == "#":
            rc[1][j][i] = 0
        elif j > 0:
            rc[1][j][i] = rc[1][j-1][i] + 1
        else:
            rc[1][j][i] = 1
    for j in range(H-1, -1, -1):
        if s[j][i] == "#":
            continue
        elif j < H-1:
            rc[1][j][i] = max(rc[1][j+1][i], rc[1][j][i])
ans = 0
for j in range(H):
    for i in range(W):
        ans = max(rc[0][j][i] + rc[1][j][i] - 1, ans)
print(ans)
### BUGGY CODE ###

def sum_dict(d, b, c):
    val = 0
    sum = 0
    if b in d:
        val = d[b]
        del d[b]
        d[c] = d.get(c, 0) + val
    for i in d.items():
        sum += (i[0] * i[1])
    return sum, d
    
n = int(input())
a = [int(x) for x in input().split()]
d = {}
for i in a:
    d[i] = d.get(i, 0) + 1
s = sum(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    s, d = sum_dict(d, b, c)
    print(s)

### FIXED CODE ###

def sum_dict(d, sum, b, c):
    val = 0
    if b in d:
        val = d[b]
        sum -= (b * val)
        del d[b]
        d[c] = d.get(c, 0) + val
        sum += (c * val)
    return sum, d
    
n = int(input())
a = [int(x) for x in input().split()]
d = {}
for i in a:
    d[i] = d.get(i, 0) + 1
s = sum(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    s, d = sum_dict(d, s, b, c)
    print(s)
### BUGGY CODE ###

import math
k = int(input())
s = 0
for i in range(k):
    a = i+1
    for j in range(k):
        b = j+1
        for l in range(k):
            c = l+1
            s += math.gcd(math.gcd(a,b),c)

print(s)

### FIXED CODE ###

import math
k = int(input())
s = 0
for i in range(k):
    a = i+1
    for j in range(k):
        b = j+1
        for l in range(k):
            c = l+1
            s += math.gcd(math.gcd(a,b),c)

print(s)
### BUGGY CODE ###

s = list(input())

while True:
  if s[0] == "A":
    break
  else:
    del s[0]
    
while True:
  if s[-1] == "Z":
    break
  else:
    del s[-1]
    
print(len(s))

### FIXED CODE ###

s = input()
print(len(s[s.find("A"):s.rfind("Z")])+1)
### BUGGY CODE ###

N = int(input()) #社員数
joushi_no_bangou = [0] #上司の社員番号
ans = []
joushi_no_bangou += map(int,input().split())

#==--------------

for i in range(N):
    if i+1 not in joushi_no_bangou:
        ans.insert(i,0)
    else:
        ans.insert(i,joushi_no_bangou.count(i+1))
for i in range(N):
    print(ans[i])

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
ct = [0] * N
     
for a in As: #ここがキモ．リスト「As」にはそれぞれの上司が入っていて，その中からaを取り出すので，a=上司になっている．これにより，ctの上司を正確に呼び出すことができる．
    ct[a-1] += 1
     
for c in ct:
    print(c)

#別解
#print(*c,sep='\n')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# C - Low Elements
import  sys

def solve152C(N, plist):
	
	count = 0
	isFound = True
	for i in range(1, N+1):
		for j in range(1, i+1):
			if plist[i-1] > plist[j-1]:
				isFound = False
				break
		if(isFound):
			count += 1
		else:
			isFound = True
					
	print(count)


if __name__ == "__main__":
	N = int(input())
	plist= list(map(int, input().split()))

	solve152C(N, plist)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# C - Low Elements
import  sys

def solve152C(N, plist):
	
	count = 1
	maxnumber = plist[0]
	minnumber = plist[0]
	isFound = True
	for i in range(2, N+1):
		p = plist[i-1]
		if p < maxnumber and p < minnumber:
			count += 1
		
		if p > maxnumber:
			maxnumber = p
		if p < minnumber:
			minnumber = p
					
	print(count)


if __name__ == "__main__":
	
	N = int(input())
	plist= list(map(int, input().split()))

	solve152C(N, plist)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)

L = list(input())
n = len(L)-1
div = 10**9+7

#階乗計算はmodを取りながら行う

def memoize(f):
  table = {}
  def func(*args):
    if not args in table:
      table[args] = f(*args)
    return table[args]
  return func

@memoize
def fact(a,n):
  ans = 1
  for i in range(1,n+1):
    ans = ans*a%div
  return ans

#ここからmain

number = 1
many = 0
for i in range(1,n+1):
  if int(L[i]) == 1:
    many += fact(3,n-i) * fact(2,number) %div
    number += 1
many += fact(2,number) + fact(3,n)

print(many%div)

### FIXED CODE ###

mod = 10**9+7

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m) (aとmは互いに素)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


L = list(input())
n = len(L)-1

#これだとTLEする

'''
number = 1
many = 0
for i in range(1,n+1):
  if int(L[i]) == 1:
    many += 3**(n-i) * 2**number %div
    number += 1
many += 2**number + 3**n
'''

beki3 = 3**n % mod
many = beki3
beki2 = 2
for i in range(1,n+1):
  beki3 = (beki3%mod)*mod_inv(3,mod)%mod
  if int(L[i]) == 1:
    many += beki3*beki2 %mod
    beki2 = beki2*2 %mod
many += beki2 % mod
print(many%mod)
### BUGGY CODE ###

from collections import deque

N = int(input())
T = [ [] for _ in range(N) ]
ans = []
for i in range(N-1):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
    ans.append([a-1,b-1])


used = [0]*N
used[0] = 1
parent = [0]*N
color = [ [0]*N for _ in range(N)]
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    c = 1
    r = q.popleft()
    for j in T[r]:
        if used[j] == 0:
            used[j] = 1
            if c == parent[r]:
                c += 1
            color[r][j] = c
            color[j][r] = c
            parent[j] = c
            c += 1
            q.append(j)
    total = max(total,c-1)


print(total)
for pair in ans:
    print(color[pair[0]][pair[1]])

### FIXED CODE ###

from collections import deque

N = int(input())
T = [ [] for _ in range(N) ]
ans = []
for i in range(N-1):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
    ans.append((a-1,b-1))


used = [0]*N
used[0] = 1
a = dict()
parent = [0]*N
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    c = 1
    r = q.popleft()
    for j in T[r]:
        if used[j] == 0:
            used[j] = 1
            if c == parent[r]:
                c += 1
            a[(r,j)] = c
            parent[j] = c
            c += 1
            q.append(j)
    total = max(total,c-1)


print(total)
for pair in ans:
    print(a[pair])
### BUGGY CODE ###

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(v, goal, graph, seen, next_v, rank):
    for x in graph[v]:
        if x in seen:
            continue
        if x == goal:
            return True
        next_v.append(x)
        rank.append(rank[0]+1)
        seen.add(x)
    return False


next_v = [0]
rank = [0]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or rank[0] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(next_v[0], N-1, graph, seen, next_v, rank):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
    rank.pop(0)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
graph = [[] for _ in range(N)] 
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(goal, graph, seen, next_v):
    for x in graph[next_v[0][0]]:
        if x == goal:
            return True
        if x in seen:
            continue
        next_v.append((x,next_v[0][1]+1))
        seen.add(x)
    return False


next_v = [(0,0)]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or next_v[0][1] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(N-1, graph, seen, next_v):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
print(ans)
### BUGGY CODE ###

from collections import Counter
from itertools import combinations

MOD = 10**9 + 7

N = int(input())
S = input()
c = Counter(S)

ans = 0

for i in range(1, len(c)+1):
    # i文字の部分文字列を考えると、i種類の文字が使われているので
    for keys in combinations(c.keys(), i):
        res = 1
        for k in keys:
            res *= (c[k])
        ans += res
        ans %= MOD

print(ans)


### FIXED CODE ###

from collections import Counter

MOD = 10**9 + 7

N = int(input())
S = input()

c = Counter(S)

ans = 1
for k in c.keys():
    ans *= c[k]+1
    ans %= MOD

ans -= 1

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

import sys
sys.setrecursionlimit(2000000)
n = int(input())
a=[[]for i in range(n)]
for i in range(n-1):
  x = int(input())
  x-=1
  a[x].append(i+1)
  
dp=[0]*n
ya = [[0,i] for i in range(n)]
def dfs(x,y):
  ya[x][0]=y
  for i in a[x]:
    dfs(i,y+1)
dfs(0,0)
ya.sort(key=lambda x:-x[0])
tmp=[]
for i in range(n):
  bb=ya[i][1]
  for j in a[bb]:
    tmp.append(dp[j])
  tmp.sort(key=lambda x:-x)
  dai =0
  for j in range(len(tmp),0,-1):
    cc=tmp.pop()
    cc+=j
    dai=max(dai,cc)
  dp[bb]=dai
print(dp[0])

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)
n = int(input())
a=[[]for i in range(n)]
for i in range(n-1):
  x = int(input())
  x-=1
  a[x].append(i+1)
  
dp=[0]*n
ya = [[0,i] for i in range(n)]
def dfs(x,y):
  ya[x][0]=y
  for i in a[x]:
    dfs(i,y+1)
dfs(0,0)
ya.sort(key=lambda x:-x[0])
tmp=[]
for i in range(n):
  bb=ya[i][1]
  for j in a[bb]:
    tmp.append(dp[j])
  tmp.sort(key=lambda x:-x)
  dai =0
  for j in range(len(tmp),0,-1):
    cc=tmp.pop()
    cc+=j
    dai=max(dai,cc)
  dp[bb]=dai
print(dp[0])
### BUGGY CODE ###

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

result = 0
tempres = 0
for i in range(0, N):
    for j in range(i, N - 1):
        if H[j] >= H[j + 1]:
            tempres += 1
        else:
            break
    result = max(result, tempres)
    i += tempres
    tempres = 0
    if result >= N - i - 1:
        break
print(result)


### FIXED CODE ###

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

result = 0
tempres = 0
for i in range(0, N):
    if tempres != 0:
        tempres -= 1
        continue
    for j in range(i, N - 1):
        if H[j] >= H[j + 1]:
            tempres += 1
        else:
            break
    result = max(result, tempres)
    if result >= N - i - 1:
        break
print(result)
### BUGGY CODE ###

h,w = map(int,input().split())
s = [input() for _ in range(h)]
dp = [[-1]*w for i in range(h)]
dp[0][0] = 1 if s[0][0]=='#' else 0
q = [[0,0]]
while q:
    x,y = q.pop()
    a = 1 if s[x][y]=='#' else 0
    if x+1<h:
        if dp[x+1][y]<0:dp[x+1][y] = dp[x][y]+a
        else:dp[x+1][y] = min(dp[x][y]+a,dp[x+1][y])
        q.append([x+1,y])
    if y+1<w:
        if dp[x][y+1]<0:dp[x][y+1] = dp[x][y]+a
        else:dp[x][y+1] = min(dp[x][y]+a,dp[x][y+1])
        q.append([x,y+1])

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



### FIXED CODE ###

h,w = map(int,input().split())
s = [input() for _ in range(h)]
dp = [[float('inf')]*w for i in range(h)]
dp[0][0] = 1 if s[0][0]=='#' else 0
for x in range(h):
    for y in range(w):
        if x+1<h:
            a = 1 if s[x][y]=='.' and s[x+1][y]=='#' else 0
            dp[x+1][y] = min(dp[x][y]+a,dp[x+1][y])
        if y+1<w:
            a = 1 if s[x][y]=='.' and s[x][y+1]=='#' else 0
            dp[x][y+1] = min(dp[x][y]+a,dp[x][y+1])

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

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

p_list=[]
cnt=[0]*(n+1)
ans=0
plt=0
for i in range(m):
    p,s=map(str,input().split())
    if s == "WA":
        cnt[int(p)] += 1;
    if s == "AC":
        if p not in p_list:
            ans+=1
            plt+=cnt[int(p)]
            p_list.insert(0,p)
        
print(str(ans) + " " + str(plt))



### FIXED CODE ###

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

p_list=[0]*(n+1)
cnt=[0]*(n+1)
ans=0
plt=0
for i in range(m):
    p,s=map(str,input().split())
    if s == "WA":
        cnt[int(p)] += 1;
    if s == "AC":
        if p_list[int(p)] == 0:
                ans+=1
                plt+=cnt[int(p)]
                p_list[int(p)] += 1
        
print(str(ans) + " " + str(plt))
### BUGGY CODE ###

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

def hash(a):
    return a%10


def check(A):
    for i in range(len(A)):
        for j in range(i, len(A)):
            if(j+1 < len(A)):
                if(A[i] == A[j+1]):
                    # print("%d=%d"%(A[i], A[j]))
                    flag = True
                    return 'NO'

    return 'YES'

arr = [[] for i in range(10)]

for i in A:
    arr[hash(i)].append(i)

for i in arr:
    flag = False
    if(check(i) == "NO"):
        print("NO")
        flag = True
        break
if(not flag):
    print("YES")

### FIXED CODE ###

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

A.sort()
# print(A)
flag = False
for i in range(len(A)):
    if(i+1 < len(A)):
        if(A[i] == A[i+1]):
            print("NO")
            flag = True
            break
if(not flag):
    print("YES")
### BUGGY CODE ###

import math
n = int(input())

for i in range(1, n+1):
  count = 0
  upper = int(math.sqrt(i))
  lower = int(math.sqrt(i/6))
  for x in range(lower, upper):
    for y in range(lower, x+1):
      for z in range(lower, y+1):
        if (x+y)**2 + (y+z)**2 + (z+x)**2 == 2*i:
          if x == y and y == z and z == x:
          	count += 1
          else:
            count += 3
            
  print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
dp = [0]*(n+1)

for x in range(1, 100):
  for y in range(1, 100):
    for z in range(1, 100):
      tmp = x*x + y*y + z*z + x*y + y*z + z*x
      if tmp <= n:
        dp[tmp] += 1

for i in range(1, n+1):
  print(dp[i])
### BUGGY CODE ###

N,K = map(int, input().split())
p = list(map(int, input().split()))
Max = []
E = 0.0

for i in range(N-(K-1)):
    if sum(Max) < sum(p[i:i+K:]):
        Max = p[i:i+K:]

for num in Max:
    E += sum(range(num+1))/num

print(E)

### FIXED CODE ###

from collections import deque
import copy
N,K = map(int, input().split())
p = list([(i+1)* i/2/i for i in map(int, input().split())])
que = deque([0]* K)
sumM = 0
sumq = 0
E = 0.0

for i in range(N):
    sumq -= que.popleft()
    sumq += p[i]
    que.append(p[i])
    if E < sumq:
        E = sumq
print(E)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
res = 0
a = [i for i in range(10)]
for num in itertools.product(a, repeat=3):
    p = 0
    for i,j in enumerate(s):
        if int(j) == num[p]:
            p += 1
            if p == 3:
                res += 1
                break
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
res = 0
a = [str(i) for i in range(10)]
for num in itertools.product(a, repeat=3):
    p = 0
    for i,j in enumerate(s):
        if j == num[p]:
            p += 1
            if p == 3:
                break
    if p == 3:
        res += 1
print(res)
### BUGGY CODE ###

k,s = map(int, input().split())
cnt = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z == s:
        cnt += 1

print(cnt)

### FIXED CODE ###

k,s = map(int, input().split())
cnt = 0
for x in range(k+1):
  for y in range(k+1):
    z = s - x -y
    if 0 <= z <= k:
      cnt += 1

print(cnt)
### BUGGY CODE ###

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

def pascal(N,K):
  C=[[0 for i in range(K+1)]for j in range(N+1)]
  for i in range(N+1):
    for j in range(K+1):
      if C[i][j]!=0:
        break
      if i==j+1 or j==1:
        C[i][j]=i
      elif i==j or j==0:
        C[i][j]=1
      else:
        C[i][j] = C[i-1][j]+C[i-1][j-1]
  return C[N][K]
    
mod = 10**9+7
x=0
for i in range(1,K+1):
  x = pascal(N-K+1,i)*pascal(K-1,i-1)
  print(x%mod)

### FIXED CODE ###

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

mod = 10**9+7
n = N-K+1
print(n)
for i in range(2,K+1):
  n = n * (N-K+2-i)*(K+1-i)//(i*(i-1))
  print(n%mod)
### BUGGY CODE ###

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

I = a.count(1)
J = a.count(2)
K = a.count(3)

dp = [[[0 for _ in range(K+1)] for __ in range(J+K+1)] for ___ in range(I+J+K+1)]

for k in range(K+1):
    for j in range(J+K+1):
        for i in range(I+J+K+1):
            if i == 0 and j == 0 and k == 0:
                continue
            if k-1 > -1 and j+1 < J+K+1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j+1][k-1]
            if j-1 > -1 and i+1 < I+J+K+1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i+1][j-1][k]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j][k]
            dp[i][j][k] += n/(i+j+k)

print(dp[I][J][K])


### FIXED CODE ###

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

I = a.count(3)
J = a.count(2)
K = a.count(1)

dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
      for ___ in range(I+1)]

for i in range(I+1):
    for j in range(I+J+1-i):
        for k in range(I+J+K+1-i-j):
            if i + j + k == 0:
                continue
            if k-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j][k-1]
            if j-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i][j-1][k+1]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j+1][k]
            dp[i][j][k] += n/(i+j+k)

print(dp[I][J][K])
### BUGGY CODE ###

from collections import deque
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

mv = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def BFS(St):
    stk = deque([St+[0]])
    seen = [[False]*W for _ in range(H)]
    while len(stk) > 0:
        l = stk.pop()
        i = l[0]
        j = l[1]
        ct = l[2]
        seen[i][j] = True
        for k in mv:
            x = i+k[0]
            y = j+k[1]
            if 0 <= x < H and 0 <= y < W:
                if S[x][y] == '.' and seen[x][y] == False:
                    stk.appendleft([x, y, ct+1])
    else:
        return(ct)


# print(BFS([2, 0], [0, 4]))


ans = 0
# 各スタート地点に対して最大距離を出力すればいいですねって話

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        ans=max(ans,BFS([i,j]))
print(ans)

### FIXED CODE ###

H, W = list(map(int, input().split()))
S =[list(input()) for _ in range(H)]
N=H*W
INF=float('inf')
L=[[INF]*N for _ in range(N)]
for i in range(N):
    h=i//W
    w=i%W
    # print(i,h,w)
    if S[h][w]=='.':
        L[i][i]=0
    if w>0 and S[h][w-1]=='.':
        L[i][i-1]=1
    if w<W-1 and S[h][w+1]=='.':
        L[i][i+1]=1
    if h>0 and S[h-1][w]=='.':
        L[i][i-W]=1
    if h<H-1 and S[h+1][w]=='.':
        L[i][i+W]=1
# print(L)

for i in range(N):
    via=L[i]
    if via[i]==INF:
        continue
    for j in range(N):
        st=L[j]
        if st[j]==INF:
            continue
        for k in range(N):
            L[j][k]=min(st[i]+via[k], st[k])
# print(L)
ans=0
for i in range(N):
    for j in range(N):
        if L[i][j]!=INF:
            ans=max(ans,L[i][j])
print(ans)
### BUGGY CODE ###

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	h = list(map(int, input().split()))
	# dpテーブル宣言: dp[今いる足場の番号-1]=[最小コスト, 足場の高さ]
	dp = [[float('inf'), h_] for h_ in h]
	dp[0][0] = 0

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(1, N):
		index_0 = max(0, n-K)
		dp[n][0] = min(
			[
				abs( h[n] - dp_[1] ) + dp_[0]
				for dp_ in set(map(tuple, dp[index_0:n]))
			]
		)
	print(dp[N-1][0])

resolve()

### FIXED CODE ###

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	# dpテーブル宣言: dp[今いる足場の番号-1]=[最小コスト, 足場の高さ]
	dp = [
		[float('inf'), int(h_)]
		for h_ in input().split()
	]
	dp[0][0] = 0
	dp[1][0] = abs(dp[0][1] - dp[1][1])

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(2, N):
		index_0 = max(0, n-K)
		h_ = dp[n][1]
		dp[n][0] = min(
			[
				abs( h_ - dp_[1] ) + dp_[0]
				for dp_ in dp[index_0:n]
			]
		)
	print(dp[N-1][0])

resolve()