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

import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, C = map(int, input().split())
    D = [[0] * (C + 1)]
    for _ in range(C):
        d = [0] + list(map(int, input().split()))
        D.append(d)

    grid = [[0] * (N + 1)]
    for _ in range(N):
        g = [0] + list(map(int, input().split()))
        grid.append(g)

    perm = permutations(range(1, C + 1), 3)
    ans = INF
    for c0, c1, c2 in perm:
        tmp = 0
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if (i + j) % 3 == 0:
                    tmp += D[grid[i][j]][c0]
                elif (i + j) % 3 == 1:
                    tmp += D[grid[i][j]][c1]
                elif (i + j) % 3 == 2:
                    tmp += D[grid[i][j]][c2]

        if tmp < ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, C = map(int, input().split())
    D = [[0] * (C + 1)]
    for _ in range(C):
        d = [0] + list(map(int, input().split()))
        D.append(d)

    grid = [[0] * (N + 1)]
    for _ in range(N):
        g = [0] + list(map(int, input().split()))
        grid.append(g)

    cost = {0: [], 1: [], 2: []}
    ans = INF
    for c in range(1, C + 1):
        cost0 = 0
        cost1 = 0
        cost2 = 0
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if (i + j) % 3 == 0:
                    cost0 += D[grid[i][j]][c]
                elif (i + j) % 3 == 1:
                    cost1 += D[grid[i][j]][c]
                elif (i + j) % 3 == 2:
                    cost2 += D[grid[i][j]][c]

        cost[0].append((c, cost0))
        cost[1].append((c, cost1))
        cost[2].append((c, cost2))

    cost[0].sort(key=lambda x: x[1])
    cost[1].sort(key=lambda x: x[1])
    cost[2].sort(key=lambda x: x[1])

    ans = INF
    for c0, cost0 in cost[0][:3]:
        for c1, cost1 in cost[1][:3]:
            for c2, cost2 in cost[2][:3]:
                if c0 == c1 or c1 == c2 or c2 == c0:
                    continue

                tmp = cost0 + cost1 + cost2
                if tmp < ans:
                    ans = tmp

    print(ans)


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

N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[[1,0,0,0,0,0,0,0,0,0]]
tmp=0
tmp1=0
tmp2=0
for i in range(0,N+1):
    dp.append([0,0,0,0,0,0,0,0,0,0])
    tmp=0
    for j in A:
        if(i-num[j]>=0):
            tmp1=dp[i-num[j]].copy()
            #存在しないなら不可
            if(tmp1[0]==0):
                continue
            tmp1[j]+=1
            tmp2=0
            for k in range(1,10):
                if(tmp1[10-k]!=0):
                    tmp2*=(10**tmp1[10-k])
                    tmp2+=(10-k)*int("1"*tmp1[10-k])
            if(tmp2>tmp):
                tmp=tmp2
                dp[i]=tmp1
ans=0
for k in range(1,10):
    if(dp[N][10-k]!=0):
        ans*=10**dp[N][10-k]
        ans+=(10-k)*int("1"*dp[N][10-k])
print(int(ans))
    


### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
if(1 in A):
    if(4 in A):
        A.remove(4)
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
if(5 in A):
    if(3 in A):
        A.remove(3)
    if(2 in A):
        A.remove(2)
if(3 in A):
    if(2 in A):
        A.remove(2)
if(9 in A):
    if(6 in A):
        A.remove(6)
if(7 in A):
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-1
    tmp_keta=-1
    for j in A:
        tmp1=-1
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]>0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            elif(dp[i-num[j]]==0):
                tmp1=j
                tmp1_keta=1

            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
                
    dp.append(tmp)
    keta.append(tmp_keta)
print(dp[N])
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
                if dest == N-1:
                    # 頂点Nがそれに該当していたら空リストを返却
                    return []
    # 問題なければ頂点リストを返却
    return res

N, M, P = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    # Pは最後に請求される、だけど、ようは動く度に支払ってると思ってもいい
    edges.append((a-1, b-1, -c+P))

res = bellman_ford(N, edges, 0)
if not len(res):
    print(-1)
else:
    # 正負を直す
    ans = -res[N-1]
    # スコアがマイナスなら0
    print(max(0, ans))


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
                if dest == N-1:
                    # 頂点Nがそれに該当していたら空リストを返却
                    return []
    # 問題なければ頂点リストを返却
    return res

N, M, P = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    # Pは最後に請求される、だけど、ようは動く度に支払ってると思ってもいい
    edges.append((a-1, b-1, -c+P))

res = bellman_ford(N, edges, 0)
if not len(res):
    print(-1)
else:
    # 正負を直す
    ans = -res[N-1]
    # スコアがマイナスなら0
    print(max(0, ans))
### BUGGY CODE ###

n = int(input())
ls = []
for i in range(n):
    ls.append(int(input()))

for i in range(n):
    lstmp = ls[0:i] + ls[i+1:]
    print(max(lstmp))


### FIXED CODE ###

n = int(input())
ls = []
for i in range(n):
    ls.append(int(input()))
maxnum = max(ls)
ind = ls.index(maxnum)
ls.remove(maxnum)
secondnum = max(ls)
ls = ls[0:ind] + [maxnum] + ls[ind:]
#print(ls)
if maxnum == secondnum:
    for i in range(n):
        print(maxnum)
    quit()
for i in range(n):
    if ls[i] == maxnum:
        print(secondnum)
    else:
        print(maxnum)
### BUGGY CODE ###

class BinaryTree:
    def __init__(self):
        self.root = None
    def b_insert(self,x):
        self.root = insert(self.root,x)
    def b_inorder(self):
        inorder(self.root)
    def b_preorder(self):
        preorder(self.root)
        
class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None
            
def insert(node,x):
    if node is None:
        return Node(x)
    elif x == node.data:
        return node
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node
def inorder(node):
    global count
    if node is None:
        return
    inorder(node.left)
    count += 1
    if count != this_len:
        print(node.data,end = " ")
    else:
        print(node.data)
    inorder(node.right)
def preorder(node):
    global count
    if node is None:
        return
    count += 1
    if count != this_len:
        print(node.data,end = " ")
    else:
        print(node.data)
    preorder(node.left)
    preorder(node.right)

length = int(input())
bfs = BinaryTree()
this_len = 0
for l in range(length):
    temp = input()
    if temp[0] == 'i':
        command,num = (n for n in temp.split(" "))
        bfs.b_insert(int(num))
        this_len += 1
    else:
        count = 0
        print("",end = " ")
        bfs.b_inorder()
        count = 0
        print("",end = " ")
        bfs.b_preorder()

### FIXED CODE ###

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, x):
        node = self.Node(x)
        if self.root is None:
            self.root = node
        else:
            here = self.root
            #
            temp = None
            while here is not None:
                temp = here
                if x < here.node:
                    here = here.left
                elif x > here.node:
                    here = here.right
            if x < temp.node:
                temp.left = node
            elif x > temp.node:
                temp.right = node

    def inorder(self, answer, address = "root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        self.inorder(answer, address.left)
        answer.append(address.node)
        self.inorder(answer, address.right)

    def preorder(self, answer, address = "root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        answer.append(address.node)
        self.preorder(answer, address.left)
        self.preorder(answer, address.right)

    class Node:
        def __init__(self, x):
            self.node = x
            self.left = None
            self.right = None

query = int(input())
bt = BinarySearchTree()
for _ in range(query):
    command = input()
    if command[0] == "i":
        bt.insert(int(command.split(" ")[1]))
    else:
        a = []
        bt.inorder(a)
        print(" ", end = "")
        print(*a)
        a = []
        bt.preorder(a)
        print(" ", end = "")
        print(*a)
### BUGGY CODE ###

n = int(input())
# h1, m1, h2, m2, k = list(map(int, input().split()))
#a, b = list(map(int, input().split()))
# a = list(map(int, input().split()))
# data = [list(map(int, input().split())) for i in range(n)]
# k = int(input())
#p = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
# py = [list(map(int, input().split())) for i in range(m)]
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
    # print(ans)
    if ans > 1000000000000000000 and not(0 in a):
        print(-1)
        exit()
print(ans)


### FIXED CODE ###

n = int(input())
# h1, m1, h2, m2, k = list(map(int, input().split()))
#a, b = list(map(int, input().split()))
# a = list(map(int, input().split()))
# data = [list(map(int, input().split())) for i in range(n)]
# k = int(input())
#p = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
# py = [list(map(int, input().split())) for i in range(m)]
a = list(map(int, input().split()))
ans = 1
if 0 in a:
    print(0)
else:
    for i in range(n):
        ans *= a[i]
        # print(ans)
        if ans > 1000000000000000000:
            print(-1)
            exit()
    print(ans)
### BUGGY CODE ###

import math

def f(h, a, b, t):
    y = 0
    for hi in h:
        if hi-b*t <= 0:
            break
        else:
            y += math.ceil((hi-b*t)/(a-b))
    if y <= t:
        return True
    else:
        return False

n, a, b = list(map(int, input().split()))
h = []
for _ in range(n):
    h.append(int(input()))
h.sort(reverse=True)

low = 1
high = math.ceil(h[0]/b)

while True:
    m = (low+high)//2
    if f(h,a,b,m):
        high = m
    else:
        low = m
    if low +1 == high:
        break

print(high)

### FIXED CODE ###

import math

def f(h, a, b, t):
    y = 0
    for hi in h:
        if hi-b*t <= 0:
            break
        else:
            y += math.ceil((hi-b*t)/(a-b))
    if y <= t:
        return True
    else:
        return False

n, a, b = list(map(int, input().split()))
h = []
for _ in range(n):
    h.append(int(input()))
h.sort(reverse=True)

low = 0
high = math.ceil(h[0]/b)

while True:
    m = (low+high)//2
    if f(h,a,b,m):
        high = m
    else:
        low = m
    if low +1 == high:
        break

print(high)
### BUGGY CODE ###

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    c1[ss]=c1.get(ss,'')+tt
    c2[tt]=c2.get(tt,'')+ss
    if len(c1[ss])<2 and len(c2[tt])<2:continue
    if set(c1[ss])==set(tt) and set(c2[tt])==set(ss):continue
    else:
        print('No')
        exit()

print('Yes')


### FIXED CODE ###

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    if c1.get(ss) is None:
        c1[ss]=tt
    if c2.get(tt) is None:
        c2[tt]=ss
    if c1[ss]==tt and c2[tt]==ss:continue
    else:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

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

def check(S, A, B):
    for i in range(N):
        for j in range(i+1, N):
            if j + B < N:
                b = j + B
            else:
                b = j + B - N
            if i + B < N:
                d = i + B
            else:
                d = i + B - N
            if S[i][b] != S[j][d]:
                return 0
    return 1

cnt = 0
for i in range(N):
    cnt += check(S, 0, i)
print(cnt * N)

### FIXED CODE ###

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

def check(S, A, B):
    for i in range(N):
        for j in range(i+1, N):
            if S[i][j] != S[j][i]:
                return 0
    return 1

cnt = 0
for i in range(N):
    cnt += check(S[i:] + S[:i], 0, i)
print(cnt * N)
### BUGGY CODE ###

from bisect import bisect_right
N,Q,*L = map(int, open(0).read().split())
D = L[3*N:]
ls = [0]*N
for i in range(N):
  s,t,x = L[3*i],L[3*i+1],L[3*i+2]
  ls[i] = (x,s,t)
ls.sort()
line = [0]*(2*N)
for i in range(N):
  x,s,t = ls[i]
  line[2*i] = (s-x,0,i)
  line[2*i+1] = (t-x,1,i)
line.sort()
road = [c[0] for c in line]
inf = [0]*(2*N)
m = 0
for i in range(2*N):
  d,p,j = line[i]
  if p:
    m -= 1<<j
  else:
    m += 1<<j
  inf[i] = m
for d in D:
  i = bisect_right(road,d)
  if i==2*N or i==0:
    print(-1)
    continue
  m = inf[i-1]
  s = m&-m
  if s==0:
    print(-1)
  else:
    ind = len(bin(s)[2:])-1
    print(ls[ind][0])

### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
M = [[] for _ in range(h)]
for i in range(h):
    M[i] = input()

D = [(-1, 0), (0, -1), (1, 0), (0, 1)]
dist = [[float("inf")] * w for _ in range(h)]
dist[sx - 1][sy - 1] = 0
q = deque()
q.append((sx - 1, sy - 1))
while q:
    X, Y = q.popleft()
    d = dist[X][Y]
    for dx, dy in D:
        nx, ny = X + dx, Y + dy
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        if M[nx][ny] == "#":
            continue
        if dist[nx][ny] <= d:
            continue
        dist[nx][ny] = d
        q.appendleft((nx, ny))
    for c in range(-2, 3):
        for r in range(-2, 3):
            nx, ny = X + c, Y + r
            if nx < 0 or ny < 0 or nx >= h or ny >= w:
                continue
            if M[nx][ny] == "#":
                continue
            if dist[nx][ny] <= d + 1:
                continue
            dist[nx][ny] = d + 1
            q.append((nx, ny))

ans = dist[gx - 1][gy - 1]
if ans == float("inf"):
    ans = -1

print(ans)


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
M = [[] for _ in range(h)]
for i in range(h):
    M[i] = input()

D = [(-1, 0), (0, -1), (1, 0), (0, 1)]
dist = [[float("inf")] * w for _ in range(h)]
dist[sx - 1][sy - 1] = 0
q = deque()
q.append((sx - 1, sy - 1))
while q:
    X, Y = q.popleft()
    d = dist[X][Y]
    for dx, dy in D:
        nx, ny = X + dx, Y + dy
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        if M[nx][ny] == "#":
            continue
        if dist[nx][ny] <= d:
            continue
        dist[nx][ny] = d
        q.appendleft((nx, ny))
    for c in range(-2, 3):
        for r in range(-2, 3):
            nx, ny = X + c, Y + r
            if nx < 0 or ny < 0 or nx >= h or ny >= w:
                continue
            if M[nx][ny] == "#":
                continue
            if dist[nx][ny] <= d + 1:
                continue
            dist[nx][ny] = d + 1
            q.append((nx, ny))

ans = dist[gx - 1][gy - 1]
if ans == float("inf"):
    ans = -1

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

# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1000000007
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

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

for i in range(N):
    dp[i][i + 1] = 0

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        dp[i][j] = min(dp[i][k] + dp[k][j] + acc[j] - acc[i] for k in range(i + 1, j))

print(dp[0][N])


### FIXED CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

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

for i in range(N):
    dp[i][i + 1] = 0

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

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

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit


@njit
def loop(N,K,A):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            temp = A[i]
            left = i - temp
            right = i + temp + 1
            if left < 0:
                left = 0
            if right > N:
                right = N
            B[left:right] += 1
        A = B
    return A


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    res = loop(N,K,A)

    print(*res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    return A


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    if K >= 43:
        M = 43
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import lil_matrix

N = int(input())
edge = lil_matrix((N,N))

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]
for key in [itemgetter(1), itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge[i1,i2] = d
    edge[i2,i1] = d

edge = edge.tocsc()

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(edge, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = [set() for _ in range(N)]
for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge[i1].add((i2,d))
    
# csr形式に直す
indptr = []
indrow = []
value = []
ptr = 0
for i in range(N):
  indptr.append(ptr)
  for j,v in edge[i]:
    indrow.append(j)
    value.append(v)
    ptr += 1
indptr.append(ptr)
value = np.array(value,dtype=int)
graph = csr_matrix((value,indrow,indptr),shape=(N,N))

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)
### BUGGY CODE ###

from itertools import accumulate
n,k = map(int,input().split())
A = list(map(int,input().split()))
for _ in range(min(k,50)):
    c = [0]*n
    for i,j in enumerate(A):
        l = max(0,i-j)
        r = min(n-1,i+j)
        c[l] += 1
        if r+1 < n:
            c[r+1] -= 1
    A = list(accumulate(c))
print(" ".join(map(str,A)))

### FIXED CODE ###

from itertools import accumulate
n,k = map(int,input().split())
A = list(map(int,input().split()))
for _ in range(min(k,50)):
    c = [0]*n
    for i,j in enumerate(A):
        l = max(0,i-j)
        r = min(n-1,i+j)
        c[l] += 1
        if r+1 < n:
            c[r+1] -= 1
    A = list(accumulate(c))
print(" ".join(map(str,A)))
### BUGGY CODE ###

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

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


### FIXED CODE ###

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

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

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