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

#関数リスト
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

h, w, k = MI()
x1, y1, x2, y2 = MI()
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1

mylist = [0] * h

#tableの読み込み
for i in range(h):
    temp = input().rstrip()
    temp = [temp[j] for j in range(w)]
    mylist[i] = temp
#初期化
distance = [[float('inf') for i in range(w)] for j in range(h)]
distance[x1][y1] = 0
d = deque()
start = [x1, y1]
goal = [x2, y2]
d.append(start)
index = 0
result = -1
move = [[-1,0],[1,0],[0,1],[0,-1]]

while d and index <= k:
    pos = d.pop()
    x = pos[0]
    y = pos[1]
    dist = distance[x][y]
    for i in move:
        #tempxの初期化
        tempx = x
        tempy = y
        for l in range(k):
            tempx += i[0]
            tempy += i[1]
            if not ((tempx >= 0 and tempx <= h-1) and (tempy >= 0 and tempy <= w - 1)):
                break
            if dist + 1 < distance[tempx][tempy] and mylist[tempx][tempy] == ".":
                distance[tempx][tempy] = dist + 1
                d.append([tempx, tempy])
            else:
                break
if distance[x2][y2] == float('inf'):
    print(-1)
else:
    print(distance[x2][y2])

### FIXED CODE ###

#関数リスト
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    h, w, k = MI()
    x1, y1, x2, y2 = MI()
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    mylist = [0] * h

    #tableの読み込み
    for i in range(h):
        temp = input().rstrip()
        temp = [temp[j] for j in range(w)]
        mylist[i] = temp
    #初期化
    distance = [[-1 for i in range(w)] for j in range(h)]
    distance[x1][y1] = 0
    d = deque()
    start = (x1, y1)
    goal = [x2, y2]
    d.append(start)
    move = ([-1,0],[1,0],[0,1],[0,-1])

    while d:
        pos = d.popleft()
        x = pos[0]
        y = pos[1]
        if x == x2 and y == y2:
            print(distance[x2][y2])
            exit()
        dist = distance[x][y]
        for i in move:
            #tempxの初期化
            tempx = x
            tempy = y
            for l in range(k):
                tempx += i[0]
                tempy += i[1]
                if not ((tempx >= 0 and tempx <= h-1) and (tempy >= 0 and tempy <= w - 1)):
                    break
                elif mylist[tempx][tempy] == "." and distance[tempx][tempy] == -1:
                    distance[tempx][tempy] = dist + 1
                    d.append((tempx, tempy))
                elif dist + 1 <= distance[tempx][tempy] and mylist[tempx][tempy] == ".":
                    distance[tempx][tempy] = dist + 1
                else:
                    break
    print(-1)            
        
main()
### BUGGY CODE ###

N, K, Q = map(int, input().split())
charanger_list = [K] * N
answer_list = []

# 正答者を記録
for i in range(Q):
	answer_list.append(int(input()) - 1)

# 点数計算
for answer in answer_list:
	charanger_list = [ charanger-1 for charanger in charanger_list]
	charanger_list[answer] += 1

for i in range(N):
	print('Yes' if charanger_list[i] > 0 else 'No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
charanger_points = [K] * N
gained_points = [0] * N

# 正答者を記録
for i in range(Q):
	gained_points[int(input()) - 1] += 1

# 点数計算
for i in range(N):
	charanger_points[i] -=  Q - gained_points[i]

# 提示
for i in range(N):
	print('Yes' if charanger_points[i] > 0 else 'No')
### BUGGY CODE ###

import numpy as np

N, C, K = map(int, input().split(" "))
T = np.sort([int(input()) for _ in range(N)])

i = 0
bus = 0
while i < N:
    bus += 1
    lst = T[i:i+C]
    i += len(lst[lst - lst[0] <= K])
print(bus)

### FIXED CODE ###

N, C, K = map(int, input().split(" "))
T = sorted([int(input()) for _ in range(N)])

bus = 0
i = 0
while i < N:
    bus += 1
    start = i
    while i < N and T[i] - T[start] <= K and i - start < C:
        i += 1
print(bus)
### BUGGY CODE ###

from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(root):
    x, y, d = root
    dp[y, x] = 0
    stack = [root]
    while stack:
        x, y, d = stack.pop()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                if dp[ny, nx] > d:
                    dp[ny, nx] = d
                    stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                if dp[ny, nx] > d+1:
                    dp[ny, nx] = d+1
                    stack.append((nx, ny, d+1))
dfs((cw-1, ch-1, 0))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

### FIXED CODE ###

from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(_) for _ in input().split()]
for iii in range(m):
  b,c=map(int,input().split())
  a+=[c]*b

a=sorted(a,reverse=True)
print(sum(a[0:n]))


### FIXED CODE ###

from heapq import heappush, heappop
n,m=map(int,input().split())
hq=[]
for _ in input().split():
  heappush(hq,(-int(_),1))
for iii in range(m):
  b,c=map(int,input().split())
  heappush(hq,(-c,b))
s=0
for iii in range(n):
  a=heappop(hq)
  s-=a[0]
  if a[1]!=1:
    heappush(hq,(a[0],a[1]-1))
print(s)
### BUGGY CODE ###

from collections import defaultdict as ddict

H,W,M=map(int,input().split())
tgts=set()
for _ in range(M):
    i,j=map(int,input().split())
    tgts.add((i,j))

rows=ddict(int)
cols=ddict(int)

ii=jj=0
ia,ja=[],[]
for i,j in tgts:
    rows[i]+=1
    cols[j]+=1
    x=rows[i]
    if x>ii:
        ii=x
        ia=[i]
    elif x==ii:
        ia.append(i)
    y=cols[j]
    if y>jj:
        jj=y
        ja=[j]
    elif y==jj:
        ja.append(j)



ans=0
for i in ia:
    for j in ja:
        k=rows[i]+cols[j]
        if (i,j) in tgts:
            k-=1
        ans=max(ans,k)

print(ans)


### FIXED CODE ###

from collections import defaultdict as ddict

ii=jj=0
ia,ja=[],[]
rows=ddict(int)
cols=ddict(int)
H,W,M=map(int,input().split())
tgts=set()
for _ in range(M):
    i,j=map(int,input().split())
    tgts.add((i,j))

    rows[i]+=1
    cols[j]+=1
    x=rows[i]
    if x>ii:
        ii=x
        ia=[i]
    elif x==ii:
        ia.append(i)
    y=cols[j]
    if y>jj:
        jj=y
        ja=[j]
    elif y==jj:
        ja.append(j)



ans=0
for i in ia:
    for j in ja:
        k=rows[i]+cols[j]
        if (i,j) in tgts:
            k-=1
        else:
            ans=k
            break
        ans=max(ans,k)

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

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

import copy,sys

def solve(pieace):
	history,frontier = set(),set()
	frontier.add(tuple(pieace))
	target_list = list(range(8))

	step = 0
	while True:
		next_frontier = set()
		for pieace in frontier:
			if all(x==y for x,y in zip(pieace,target_list)):
#				print([(x,y) for x,y in zip(pieace,target_list)])
				return step
			zero_position = pieace.index(0)
			relative = zero_position%4

			new_peiace = list(copy.deepcopy(pieace))
			new_peiace[relative],new_peiace[relative+4] = new_peiace[relative+4],new_peiace[relative]
			new_peiace = tuple(new_peiace)
			if new_peiace not in history:
				next_frontier.add(new_peiace)

			if relative in [0,1,2]:
				new_peiace = list(copy.deepcopy(pieace))
				new_peiace[zero_position],new_peiace[zero_position+1] = new_peiace[zero_position+1],new_peiace[zero_position]
				new_peiace = tuple(new_peiace)
				if new_peiace not in history:
					next_frontier.add(new_peiace)
			if relative in [1,2,3]:
				new_peiace = list(copy.deepcopy(pieace))
				new_peiace[zero_position],new_peiace[zero_position-1] = new_peiace[zero_position-1],new_peiace[zero_position]
				new_peiace = tuple(new_peiace)
				if new_peiace not in history:
					next_frontier.add(new_peiace)
		history |= frontier
		frontier = next_frontier
		step += 1

def main():
	line = input().strip()
	while line!='':
		pieace = list(map(int,line.split(' ')))
		print(solve(pieace))
		line = input().strip()

if __name__=='__main__':
	main()

### FIXED CODE ###

from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
	v=q.pop(0)
	coor=m[''.join(v)][0]
	x=coor%X
	y=coor//X
	depth=m[''.join(v)][1]
	nextstr=''.join(v)
	if 0<x:
		v[coor],v[coor-1]=v[coor-1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'R']
		v[coor],v[coor-1]=v[coor-1],v[coor]
	if x<X-1:
		v[coor],v[coor+1]=v[coor+1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'L']
		v[coor],v[coor+1]=v[coor+1],v[coor]
	if 0<y:
		v[coor],v[coor-X]=v[coor-X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'D']
		v[coor],v[coor-X]=v[coor-X],v[coor]
	if y<Y-1:
		v[coor],v[coor+X]=v[coor+X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'U']
		v[coor],v[coor+X]=v[coor+X],v[coor]

try:
	while True:
		v=raw_input().split()
		print(m[''.join(v)][1])
except EOFError:
	pass
### BUGGY CODE ###

import itertools
import math

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

mod = 10**9+7

# print(list(itertools.combinations(range(6), 3)))
# A = range(6)
# N = 6
# K = 3

# 二項係数を素数で割った余り
def combMod(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    # fact = [-1 for _ in range(n+1)]
    # fact[0] = 1
    # fact[1] = 1
    # inv = [-1 for _ in range(n+1)]
    # inv[0] = 0
    # inv[1] = 1
    # factinv = [-1 for _ in range(n+1)]
    # factinv[0] = 1
    # factinv[1] = 1
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    for i in range(2, n + 1):
        # fact[i] = ((fact[i-1] * i) % p)
        # inv[i] = ((-inv[p % i] * (p // i)) % p)
        # factinv[i] = ((factinv[i-1] * inv[i]) % p)
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)


    return fact[n] * factinv[r] * factinv[n-r] % p


ans = 0
for i in range(N):
    # ans += (combMod(i, K-1, mod) - combMod(N-i-1, K-1, mod)) * A[i] % mod
    ans += combMod(i, K-1, mod) * A[i] % mod
    ans -= combMod(N-i-1, K-1, mod) * A[i] % mod

print(ans%mod)

### FIXED CODE ###

# import itertools
# import math

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

mod = 10**9+7

# print(list(itertools.combinations(range(6), 3)))
# A = range(6)
# N = 6
# K = 3

# 二項係数を素数で割った余り
def combMod(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
    # fact = [-1 for _ in range(n+1)]
    # fact[0] = 1
    # fact[1] = 1
    # inv = [-1 for _ in range(n+1)]
    # inv[0] = 0
    # inv[1] = 1
    # factinv = [-1 for _ in range(n+1)]
    # factinv[0] = 1
    # factinv[1] = 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
p = mod
    
for i in range(2, N + 1):
    # fact[i] = ((fact[i-1] * i) % p)
    # inv[i] = ((-inv[p % i] * (p // i)) % p)
    # factinv[i] = ((factinv[i-1] * inv[i]) % p)
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)




ans = 0
for i in range(N):
    num = combMod(i, K-1, mod) % mod
    ans += num * A[i] % mod
    ans -= num * A[N-i-1] % mod
    ans %= mod

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

import collections
N = int(input())
S = [input() for i in range(N)]
s = collections.Counter(S) #出現回数をまとめた辞書型作成

dict = sorted(key for key,value in s.items() if value==max(s.values()))
for d in dict:
    print(d)

### FIXED CODE ###

#bA
import collections
N = int(input())
S = [input() for i in range(N)]
s = collections.Counter(S) #出現回数をまとめた辞書型作成

maximum = max(s.values()) #
list = sorted(key for key,value in s.items() if value==maximum)
#sを利用して、出現回数が最大のものを辞書順に並べたリストを作成

for i in list:
    print(i)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
edge = []
S = [list(input()) for i in range(H)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] == "#" :
        continue
    else :
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return max(dist)

ans = 0
for i in range(H*W) :
    dist = [-1 for _ in range(H*W)]
    ans = max(ans, bfs(i))

print(ans)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
edge = []
S = [list(input()) for i in range(H)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] != "#" :
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return max(dist)

ans = 0
for i in range(H*W) :
    if S[i//W][i%W] != "#" :
        dist = [-1 for _ in range(H*W)]
        ans = max(ans, bfs(i))

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

iN,iT = [int(_) for _ in input().split()]
aA = [int(_) for _ in input().split()]
iL = len(aA)

aMaxD = [0]
aMin=[aA[0]]
iV = 0

def checkMax(aMaxD,aMin,iB):
    iMaxD = 0
    for iMin in aMin:
        iMaxD = max(iMaxD,iB - iMin)
    if aMaxD[0] < iMaxD:
        aMaxD = [iMaxD]
    elif aMaxD[0] == iMaxD:
        aMaxD.append(iMaxD)
    return aMaxD

for i in range(1,iL):
    iB = aA[i-1]
    iN = aA[i]
    if iB - iN > 0:
        if iV >= 0:
            aMaxD = checkMax(aMaxD,aMin,iB)
        iV = -1
    elif iB - iN < 0:
        if iV <= 0:
            aMin.append(iB)
        if i == iL -1 :
            aMaxD = checkMax(aMaxD,aMin,iN)
        iV = 1
print( len(aMaxD) )


### FIXED CODE ###


iN,iT = [int(_) for _ in input().split()]
aA = [int(_) for _ in input().split()]
iL = len(aA)

aMaxD = [0]
iMin = aA[0]
iV = 0

def checkMax(aMaxD,iMaxD):
    if aMaxD[0] < iMaxD:
        aMaxD = [iMaxD]
    elif aMaxD[0] == iMaxD:
        aMaxD.append(iMaxD)
    return aMaxD

for i in range(1,iL):
    iB = aA[i-1]
    iN = aA[i]
    if iB - iN > 0:
        if iV >= 0:
            aMaxD = checkMax(aMaxD,iB-iMin)
        iV = -1
    elif iB - iN < 0:
        if iV <= 0:
            iMin = min(iB,iMin)
        iV = 1
aMaxD = checkMax(aMaxD,aA[-1] - iMin)
print( len(aMaxD) )
### BUGGY CODE ###

import re
n, q = map(int, input().split())
S = input()
for i in range(q):
    l, r = map(int, input().split())
    match = re.findall("(AC)", S[l-1:r])
    print(len(match))

### FIXED CODE ###

n, q = map(int, input().split())
S = input()
t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = t[i] + (1 if S[i : i+2] == "AC" else 0)

for i in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

def euqlid(x,y):
    if x < y:
        tmp = x
        x  = y
        y = tmp
    while x % y != 0:
        tmp = x % y
        x = y
        y = tmp
    return y
a, b = map(int, input().split())
k = euqlid(a, b)
data = set([1])
i = 2
while k > 1:
    flag = False
    while k % i == 0:
        k = k // i
        flag = True
    if flag:
        data.add(i)
    i += 1
print(len(data))

### FIXED CODE ###

import math
def euqlid(x,y):
    while x % y != 0:
        tmp = x % y
        x = y
        y = tmp
    return y
a, b = map(int, input().split())
if a < b:
    tmp = a
    a = b
    b = tmp
k = euqlid(a, b)
sum = 0
i = 2
if k == 1:
    print(1)
    exit()
while i <= math.sqrt(k):
    flag = False
    while k % i == 0:
        k = k // i
        flag = True
    if flag:
        sum += 1
    i += 1
if i <= k:
    sum += 1
print(sum + 1)
### BUGGY CODE ###

p=lambda x:print(x,end=' ')
n=input()
p(n+':')
n=int(n);s=n**.5
while n%2==0 and n>3:
    p(2)
    n//=2
d=3
while n>d+1:
    if s>d and n%d==0:
        p(d)
        n//=d
    else:d+=2
print(n)


### FIXED CODE ###

p=lambda x:print(x,end=' ')
n=input();p(n+':')
m=n=int(n)
while n%2==0 and n>3:p(2);n//=2
d=3
while d*d<m and n>d:
 if n%d>0:d+=2
 else:p(d);n//=d
print(n)
### BUGGY CODE ###

h,n=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(n)]

length=h+max(AB)[0]
DP=[float("inf")]*length
DP[0]=0

for i in range(h):
    for a,b in AB:
        DP[i+a]=min(DP[i+a],DP[i]+b)

print(min(DP[h:]))

### FIXED CODE ###

h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print(min(DP[h:]))
### BUGGY CODE ###

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

from bisect import insort
while M>0:
  a = A.pop()
  a /= 2
  insort(A,a)
  M-=1
ans = 0
for a in A:
  ans += int(a)
print(ans)
  

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(lambda x: -int(x),input().split()))
import heapq
heapq.heapify(A)
for _ in range(M):
  a = heapq.heappop(A)
  a /= 2
  heapq.heappush(A,a)
ans = 0
for a in A:
  ans += int((-1)*a)
print(ans)
### BUGGY CODE ###

n, W = list(map(int, input().split()))
w = [0 for i in range(n)]
v = [0 for i in range(n)]
for i in range(n):
    w[i], v[i] = list(map(int, input().split()))
dp = [[0 for i in range(W +1)] for j in range(n)]
for j in range(W+1):
    for i in range(n):
        if j - w[i] >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
        else:
            dp[i][j] =  dp[i - 1][j]
print(dp[-1][-1])


### FIXED CODE ###

n, W = list(map(int, input().split()))
w = [0 for i in range(n + 1)]
v = [0 for i in range(n + 1)]
for i in range(n):
    w[i + 1], v[i + 1] = list(map(int, input().split()))
dp = [[0 for i in range(W+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(1,W+1):
        if w[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
print(int(dp[n][W]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 10 ** 9
for i in range(n):
    b = a[i] - (i+1)
    f = 0
    for j in range(n):
        f += abs(a[j] - (b + j + 1))
    ans = min(f,ans)
print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = [A[i] - (i+1) for i in range(n)]
B.sort()
b = B[n//2]
f = 0
for i in range(n):
    f += abs(B[i] - b)
print(f)