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

from array import array

def main():
    n,K = map(int, input().split())
    h = list(map(int, input().split()))
    inf = 1<<60
    DP = [array("q", [inf]*(K+1)) for i in range(K+1)]
    DP[0][0] = 0
    for i in range(n):
        hi = h[i]
        nxt = [array("q", [inf]*(K+1)) for i in range(K+1)]
        for j in range(min(i+1, K+1)):
            for k in range(j+1):
                l = i-k-1
                if l<0:
                    left = 0
                else:
                    left = h[l]
                a = hi-left if left<hi else 0
                nxt[j][0] = min(nxt[j][0], DP[j][k]+a)
                if j == K:
                    continue
                nxt[j+1][k+1] = min(nxt[j+1][k+1], DP[j][k])
        DP = nxt

    ans = float("inf")
    for i in DP:
        ans = min(ans, min(i))
    print(ans)

main()

### FIXED CODE ###

def main():
    n,K = map(int, input().split())
    h = list(map(int, input().split()))

    DP = [[float("inf")]*(K+1) for i in range(K+1)]
    DP[0][0] = 0
    for i in range(n):
        hi = h[i]
        nxt = [[float("inf")]*(K+1) for i in range(K+1)]
        for j in range(min(i+1, K+1)):
            for k in range(j+1):
                l = i-k-1
                if l<0:
                    left = 0
                else:
                    left = h[l]
                a = hi-left if left<hi else 0
                nxt[j][0] = min(nxt[j][0], DP[j][k]+a)
                if j == K:
                    continue
                nxt[j+1][k+1] = min(nxt[j+1][k+1], DP[j][k])
        DP = nxt

    ans = float("inf")
    for i in DP:
        ans = min(ans, min(i))
    print(ans)

main()
### BUGGY CODE ###

n = int(input())
s = input()

keys = []

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            keys.append(''.join([s[i], s[j], s[k]]))

print(len(set(keys)))


### FIXED CODE ###

n = int(input())
s = input()

keys = []

for i in range(10):
    i_str = str(i)
    if i_str not in s:
        continue
    else:
        t = s[s.index(i_str)+1:]
        for j in range(10):
            j_str = str(j)
            if j_str not in t:
                continue
            else:
                u = t[t.index(j_str)+1:]
                for k in range(10):
                    k_str = str(k)
                    if k_str in u:
                        keys.append(i_str + j_str + k_str)

print(len(keys))
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    x, y = LI()
    G[x - 1] += [y - 1]
    G[y - 1] += [x - 1]


par = [-1] * n
def f(u):
    b, w = 1, 1
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        cb, cw = f(v)
        b = b * cw % mod
        w = w * (cw + cb)
    return b, w

bb, ww = f(0)
print((bb + ww) % mod)

### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    x, y = LI()
    G[x - 1] += [y - 1]
    G[y - 1] += [x - 1]


par = [-1] * n
def f(u):
    b, w = 1, 1
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        cb, cw = f(v)
        b = b * cw % mod
        w = w * (cw + cb)
    return b, w

bb, ww = f(0)
print((bb + ww) % mod)
### BUGGY CODE ###

n = int(input())
nn = list(map(int,input().split()))
import numpy as np

l = np.sort(nn)

for i in l:
  print(nn.index(i)+1)


### FIXED CODE ###

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

import numpy as np

ll = np.array(nn)
p = list(ll.argsort())

for i in p:
  print(i+1)
### BUGGY CODE ###

# Acceptance of input
import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

max_d = 1001
adj = [[max_d] * V for i in range(V)]

for line in file_input:
    s, t, d = map(int, line.split())
    adj[s][t] = d

max_path = 15001
dp = [[max_path] * (1 << V) for i in range(V)]
dp[0][0] = 0

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        return None
    
    for t, d in enumerate(adj[v]):
        if b & (1 << t) or d == max_d:
            continue
        mask = b | (1 << t)
        t_d = dp[v][b] + adj[v][t]
        if dp[t][mask] > t_d:
            dp[t][mask] = t_d
            tsp(t, mask)

# Output
tsp(0, 0)

ans = dp[0][-1]
if ans == max_path:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

no_route = 15001

# (v-1) th vertex is excluded
dp = [[no_route] * (V - 1) for i in range(1 << (V - 1))]

adj = [[] for i in range(V)]

for line in file_input:
    s, t, d = map(int, line.split())
    if s == V - 1:
        # Record the distance from the (v-1) th vertex to the adjacent vertex
        dp[1 << t][t] = d
    else: 
        # Store distance from source, not target
        adj[t].append((s, d))

# DP
for b in range(1, 1 << (V - 1)):
    for i in range(V - 1):
        b_i = 1 << i
        if b & b_i:
            pre_bit = b ^ b_i
            dp_pre = dp[pre_bit]
            for s, d in adj[i]:
                pre_rec = dp_pre[s]
                if pre_rec != no_route:
                    dp[b][i] = min(dp[b][i], pre_rec + d)

ans = no_route

# A state where all vertices other than (v-1) have been visited.
dp_comp = dp[(1 << (V - 1)) - 1]

for s, d in adj[V - 1]:
    comp_rec = dp_comp[s]
    if comp_rec != no_route:
        ans = min(ans, comp_rec + d)

if ans == no_route:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n=int(input())
dic={}
for _ in range(n):
	s=list(input())
	s.sort()
	s=''.join(s)
	if s not in dic.keys():
		dic[s]=1
	else:
		dic[s]+=1
	ans=0
	for (k,v) in dic.items():
		ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
n=int(input())
dic=defaultdict(int)
for _ in range(n):
	s=list(input())
	s.sort()
	s=''.join(s)
	dic[s]+=1
ans=0
for (k,v) in dic.items():
	ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

import sys

def add_x2y(x, y, d, key2rep):
    rep = key2rep[y]
    big_rep = key2rep[x]
    if rep == big_rep:
        return
    for old in d[big_rep]:
        d[rep].add(old)
        key2rep[old] = rep

N, M = map(int,input().split(' '))
p_list = [int(i) for i in input().split(' ')]
d = {i+1:set([i+1]) for i in range(N)}
key2rep = {i+1:i+1 for i in range(N)}

for line in sys.stdin:
    x,y = map(int, line.strip().split(' '))
    add_x2y(max(x,y), min(x,y), d, key2rep)

print(len([1 for i in range(N) if p_list[i] in d[key2rep[i+1]]]))



### FIXED CODE ###

import sys

def key2rep_iter(key, key2rep, temp_list):
    if key2rep[key] == key:
        for i in temp_list:
            key2rep[i] = key2rep[key]
        return key
    temp_list.append(key)
    return key2rep_iter(key2rep[key], key2rep, temp_list)

def add_x2y(x, y, key2rep):
    rep = key2rep_iter(y, key2rep, [])
    big_rep = key2rep_iter(x, key2rep, [])
    if rep == big_rep:
        return
    key2rep[big_rep] = rep

N, M = map(int,input().split(' '))
p_list = [int(i) for i in input().split(' ')]
key2rep = {i+1:i+1 for i in range(N)}

for line in sys.stdin:
    x,y = map(int, line.strip().split(' '))
    add_x2y(max(x,y), min(x,y), key2rep)

print(len([1 for i in range(N) if key2rep_iter(p_list[i], key2rep, []) == key2rep_iter(i+1, key2rep, [])]))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
bc = []
for _ in range(M):
  b, c = map(int, input().split())
  bc += [c]*b
A = sorted(A)
bc = sorted(bc, reverse=True)

for i in range(min(len(bc), N)):
  if bc[i] > A[i]:
    A[i] = bc[i]

print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x:x[1], reverse=True)
st = 0
flag = True
for i in range(m):
  b, c = bc[i]
  if flag and st < n:
    for i in range(st, min(b+st, n)):
      if a[i] < c:
        a[i] = c
      else:
        flag = False
        break
    st += b
  else:
    break

print(sum(a))
### BUGGY CODE ###

a,b,c,k=map(int,input().split())
n1=1
n2=0
if a==b:print(0);exit()
for i in range(k):
    n1,n2=n2*2,n1+n2
    if (n1-n2)*(a-b)>10**18:print("Unfair");exit()
print((n1-n2)*(a-b))

### FIXED CODE ###

a,b,c,k=map(int,input().split())
t=-1
if k%2==0:t=1
print(t*(a-b))
### BUGGY CODE ###

from collections import deque
#定数
#3≦n≦2*10^3
n, x, y = map(int, input().split())

#答えの計算
A = [0 for i in range(n)]   #Answers
for i in range(n):  #O(n)
    Q = deque([i])  #Queue BFSのためのもの
    #Record 位置iからの距離を記録
    R = [-1 for i in range(n)]  
    R[i] = 0
    #BFS O(n)
    while len(Q) != 0:
        t = Q[0]    #target
        d = R[t]    #distance(target)
        Q.popleft()
        #Queueに値を入れるとともに距離を更新する
        def push_and_record(t:int, d:int):
            if R[t] < 0:
                R[t] = d
                Q.append(t)
            else:
                pass
        #+方向
        if t < n-1:
            push_and_record(t+1, d+1)
        else:
            pass
        #-方向
        if t > 0:
            push_and_record(t-1, d+1)
        else: 
            pass
        #xとy
        if t == x-1:
            push_and_record(y-1, d+1)
        elif t == y-1:
            push_and_record(x-1, d+1)
        else:
            pass
    #Ansに距離の結果を入れる
    for i in range(n):
        A[R[i]] += 1

#答えの出力
for i in range(1, n):
    print(A[i] // 2)    #組み合わせ

### FIXED CODE ###

from collections import deque
n, x, y = map(int, input().split())

def push(v, d):
    if Dist[v] == -1:   #距離未更新
        Dist[v] = d
        Queue.append(v)
    else:   #距離が更新済み
        pass
    return 0
    
Ans = [0] * n
for i in range(n):
    Queue = deque([i])
    Dist = [-1] * n
    Dist[i] = 0 
    while len(Queue) != 0:
        v = Queue[0]
        d = Dist[v]
        #辺を通して次の頂点へ

        #-方向
        if v-1 >= 0:
            push(v-1, d+1)
        else:
            pass

        #+方向
        if v+1 < n:
            push(v+1, d+1)
        else:
            pass

        #XとYの間
        if v == x-1 :
            push(y-1, d+1)
        elif v == y-1:
            push(x-1, d+1)
        else:
            pass
        Queue.popleft()
    for i in Dist:
        Ans[i] += 1

for i in range(len(Ans)):
    Ans[i] *= 0.5

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

import bisect

N = int(input())
numbers = []
for i in range(N):
    numbers.append(int(input()))

lis = [numbers[0]]
for last in numbers[1:]:
    pos = bisect.bisect_left(lis, last)
    if len(lis) < pos:
        lis.append(last)
    else:
        lis = lis[:pos] + [last] + lis[pos+1:]

print(len(lis))

### FIXED CODE ###

import bisect

N = int(input())
numbers = []
for i in range(N):
    numbers.append(int(input()))

lis = [numbers[0]]
for last in numbers[1:]:
    if lis[-1] < last:
        lis.append(last)
    else:
        pos = bisect.bisect_left(lis, last)
        lis[pos] = last

print(len(lis))
### BUGGY CODE ###

# N個のimosなので二次元でやる 0.5がうざいので*2する( (2*10^5) * C )

# なぜか2WAが取れない

# 嘘解法？

N, C = map(int, input().split())
x = 2 * (10**5)
# x = 30  # test
imos = [[0 for _ in range(x)] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    s, t, c = s * 2 - 1, t * 2 - 1, c - 1
    imos[c][s - 1] += 1
    imos[c][t] -= 1

for i in range(C):
    for j in range(1, x):
        imos[i][j] += imos[i][j - 1]
        imos[i][j] = min(1, imos[i][j])  # test

ans = 0
for j in range(x):
    tmp = 0
    for i in range(C):
        tmp += imos[i][j]
    ans = max(ans, tmp)
# print("-----------")
# for x in imos:
#     print(x)
print(ans)

# 1 3
# 3 4 2


### FIXED CODE ###

# N個のimosなので二次元でやる 0.5がうざいので*2する( (2*10^5) * C )

# なぜか2WAが取れない

# これ嘘解法ぽい気がする

N, C = map(int, input().split())
x = 2 * (10**5)
# x = 30  # test
imos = [[0 for _ in range(x)] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    s, t, c = s * 2 - 1, t * 2 - 1, c - 1
    imos[c][s - 1] += 1
    imos[c][t] -= 1
    # imos[c][s - 1] = min(1, imos[c][s - 1])  # test

for i in range(C):
    for j in range(1, x):
        imos[i][j] += imos[i][j - 1]
        # imos[i][j] = min(1, imos[i][j])  # test

ans = 0
for j in range(x):
    tmp = 0
    for i in range(C):
        tmp += min(1, imos[i][j])
    ans = max(ans, tmp)
# print("-----------")
# for x in imos:
#     print(x)
print(ans)

# 1 3
# 3 4 2
### BUGGY CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split())) + [2**26 for _ in range(k)]

dist = [2**26 for _ in range(n+k)]
dist[n-1]= 0
for x in range(n-2,-1,-1):
    a = l[x]
    dist[x] = min(dist[y] + abs(a-l[y]) for y in range(x+1,x+1+k))
print (dist[0])


### FIXED CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split())) + [2**26 for _ in range(k)]

dist = [2**26 for _ in range(n+k)]
dist[n-1]= 0
for x in range(n-2,-1,-1):
    a = l[x]
    #dist[x] = min(dist[y] + abs(a-l[y]) for y in range(x+1,x+1+k))
    dist[x] = min(y + abs(a-b) for b,y in zip(l[x+1:x+1+k],dist[x+1:x+1+k]))
print (dist[0])
### BUGGY CODE ###

def solve(a, b, c):
    sm = 0
    while True:
        if (c - b * sm) % (a - b) == 0:
            x = (c - b * sm) // (a - b)
            if 0 <= x <= sm:
                return x, sm - x
        sm += 1

n = int(input())
t, a = [int(x) for x in input().split()]
for i in range(1, n):
    t2, a2 = [int(x) for x in input().split()]
    x, y = solve(a2, -t2, a * t2 - t * a2)
    t, a = t + x, a + y

print(t + a)


### FIXED CODE ###

import math
from fractions import Fraction

n = int(input())
t, a = [int(x) for x in input().split()]
for i in range(1, n):
    t2, a2 = [int(x) for x in input().split()]
    x = math.ceil(max(Fraction(t, t2), Fraction(a, a2)))
    t, a = x * t2, x * a2

print(t + a)
### BUGGY CODE ###

n = int(input())
a = [0]
a.extend(list(map(int,input().split())))
a.append(0)

cost = []

for i in range(n):
  cost.append(abs(a[i+1]-a[i]))
cost.append(abs(a[-2]))

for i in range(n):
  print(sum(cost) - cost[i]- cost[i+1] + abs(a[i+2]-a[i]))

### FIXED CODE ###

n = int(input())
a = [0]
a.extend(list(map(int,input().split())))
a.append(0)

cost = []

for i in range(n):
  cost.append(abs(a[i+1]-a[i]))
cost.append(abs(a[-2]))

s_cost = sum(cost)
for i in range(n):
  print(s_cost - cost[i]- cost[i+1] + abs(a[i+2]-a[i]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
_a = set(a)
for x in _a:
    y = a.count(x)
    if y < x:
        ans += y
    elif y > x:
        ans += y - x
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
c = Counter(a)
for key in c:
    if c[key] < key:
        ans += c[key]
    elif c[key] > key:
        ans += c[key] - key
print(ans)
### BUGGY CODE ###


from collections import defaultdict

S = input()
n = len(S)

mod = 2019
d = defaultdict(int)
d[0] = 1
num = 0
for i in reversed(range(n)):
    num += int(S[i]) * 10 ** (n - i - 1)
    d[num % mod] += 1

ans = 0
for v in d.values():
    ans += v * (v - 1) // 2
print(ans)


### FIXED CODE ###


S = list(map(int, list(input())))

mod = 2019
ctr = [0] * mod
t = 0
for i, v in enumerate(reversed(S)):
    t = (t + int(v) * pow(10, i, mod)) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr:
    ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
a = [0] * n
li = [0] * (n-1)
for i in range(n):
    a[i] = int(input())
for i in range(n):
    li_s = a[:i]
    li_g = a[i+1:]
    li_max = max(li_s,li_g)
    print(max(li_max))

### FIXED CODE ###

n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())
sorted_a = sorted(a, reverse=True)
max_a = sorted_a[0]
for i in range(n):
    if max_a != a[i]:
        print(max_a)
    else:
        print(sorted_a[1])
### BUGGY CODE ###

######## 関数 ############

def find_max(A):
    max = A[0]
    max_index = 0
    for i in range(len(A)):
        if A[i] > max:
            max_index = i
            max = A[i]
    return max_index

##### プログラム ###############

# 入力を受け取る
N, M = input().strip().split()
N, M = [int(N), int(M)]
A = input().strip().split()
A = list(map(int, A))     # 整数に変換

for i in range(M): # 各割引券1枚ずつ、一番高い品物に使っていく
    max_i = find_max(A)  # O(N)
    A[max_i] //= 2  # 割引券1枚で50% OFF

total_price = 0
for i in range(N):
    total_price += A[i]

print(total_price)

### FIXED CODE ###

import heapq

######## クラス ############
class MaxHeap:
    def __init__(self, H=[]):
        self.heapify(H)

    def heapify(self, H):
        self._neg_heap = [ -a for a in H ] # マイナスをかける
        heapq.heapify( self._neg_heap )

    def push(self, value):
        heapq.heappush(self._neg_heap, -value)

    def pop(self):
        return (-1) * heapq.heappop(self._neg_heap)

    def get_heap(self):
        return [ -a for a in self._neg_heap ]



##### プログラム ###############

# 入力を受け取る
N, M = input().strip().split()
N, M = [int(N), int(M)]
A = input().strip().split()
A = [int(a) for a in A] # 整数に変換

price_heap = MaxHeap(A)

i = 0
for i in range(M):# 各割引券1枚ずつ、一番高い品物に使っていく
    price = price_heap.pop() # 一番高い品物
    price //= 2  # 一番高い商品に割引券を使って半額にする
    price_heap.push(price) # 半額になった商品をheapに戻す
    i += 1

total_price = 0
new_prices = price_heap.get_heap()

for i in range(N):
    total_price += new_prices[i]

print(total_price)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

h,w = map(int,input().split())

matrix = [[1]*(w+2)]
matrix += [[1] + [x == '#' for x in input().rstrip()] + [1] for _ in range(h)]
matrix.append([1]*(w+2))

matrix_list1 = deque()
cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j]:
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if not matrix[x+1][y]:
            matrix[x+1][y] = 1
            matrix_list1.append([x+1,y])
        if not matrix[x-1][y]:
            matrix[x-1][y] = 1
            matrix_list1.append([x-1,y])
        if not matrix[x][y+1]:
            matrix[x][y+1] = 1
            matrix_list1.append([x,y+1])
        if not matrix[x][y-1]:
            matrix[x][y-1] = 1
            matrix_list1.append([x,y-1])
    cnt += 1
    
print(cnt)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
WV = (map(int, input().split()) for _ in range(N))

DP = [0] * (W+1)

for w, v in WV:
  for j in range(W, w-1, -1):
    dp = DP[j-w] + v 
    if DP[j] < dp:
      DP[j] = dp
print(max(DP))


### FIXED CODE ###

def dp():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))

  DP = [0] * (W+1)
  for w, v in WV:
    for j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print(dp())
### BUGGY CODE ###

from collections import deque
import numpy as np

def main():
  N=int(input())
  S=list(map(int,input().split()))
  count=0
  P=np.ones((N*N+1))
  d=np.zeros((N*N+1))
  que=deque()
  for i in range(N*N):
    player=S[i]
    P[player]=0
    que.clear()
    que.append((player,0))
    d[player]=i+1

    while que:
      kouho,j=que.popleft()
      if kouho%N==0:
        break
      if kouho%N==1:
        break
      if kouho+N>N*N:
        break
      if kouho<N:
        break

      if d[kouho+N]<i+1:
        if P[kouho+N]==1:
          que.append((kouho+N,j+1))
          d[kouho+N]=i+1
        else:
          que.appendleft((kouho+N,j))
          d[kouho+N]=i+1

      if d[kouho-N]<i+1:
        if P[kouho-N]==1:
          que.append((kouho-N,j+1))
          d[kouho-N]=i+1
        else:
          que.appendleft((kouho-N,j))
          d[kouho-N]=i+1

      if d[kouho+1]<i+1:
        if P[kouho+1]==1:
          que.append((kouho+1,j+1))
          d[kouho+1]=i+1
        else:
          que.appendleft((kouho+1,j))
          d[kouho+1]=i+1

      if d[kouho-1]<i+1:
        if P[kouho-1]==1:
          que.append((kouho-1,j+1))
          d[kouho-1]=i+1
        else:
          que.appendleft((kouho-1,j))
          d[kouho-1]=i+1
    count+=j

  print(count)

main()


### FIXED CODE ###

from numba import njit
import numpy as np

@njit
def main(N, P):
    lista = [1, -1, N, -N]
    d = np.zeros((N, N), dtype=np.int32)
    d = d.ravel()
    sit = np.ones_like(d)
    stack = np.empty_like(d)
    count = 0
    for i in range(N*N):
        d[i] = min(i % N, (N-1-i) % N, i//N, N-1-i//N)
    for player in P:
        sit[player-1] = 0
        count += d[player-1]
        stack[0] = player
        num = 0
        while num >= 0:
            p = stack[num]
            num -= 1
            a = d[p-1]+sit[p-1]
            for i in lista:
                if p+i < 1 or p + i > N*N:
                    continue
                if d[p+i-1] > a:
                    d[p+i-1] = a
                    num += 1
                    stack[num] = p+i
    print(count)

N = int(input())
P = np.array(input().split(), np.int32)

main(N, P)