题目描述

在一个 $\red{n×}$$\red{n}$的棋盘上,每个格子都写着$\red{1\sim}$$\red{n^2 }$的数字且两两不同.你有三个棋子,马,象,车.

首先,你可以选择三个棋子中的一个放在写了数字$\red{1}$的格子上,然后依次到达写了数字为$\red{2}$的格子,数字为$\red{3}$的格子,...一直到数字为 $\red{n^2}$的格子.

每一次操作你可以选择按照国际象棋的走法走一步,或者把当前的棋子换成另外一个棋子.

每一个格子可以到达任意次. 国际象棋中,马走"日"字,象可以沿着斜着的对角线走不限格数,车可以水平或者竖直走不限格数.

求从写着$\red{1}$的格子开始,依次遍历所有数字,到达写着数字 $\red{n^2}$的格子,你希望最小化总操作次数.

在总操作次数一定时,最小化替换棋子的次数.

输入格式

第一行输入一个整数 $\red{n，}$表示棋盘边长。

接下来 $\red{n}$行，第$\red{i}$行$\red{n}$个整数$\red{a_{i1},a_{i2},...a_{in},}$表示第$\red{i}$行填的数字.

输出格式

两个整数，表示最优情况下,最少的总操作次数以及此时的最小替换棋子次数

样例

输入样例

3

1 9 3 

8 6 7 

4 2 5

输出样例

12 1

提示

对于$\red{50\%}$的数据满足, $\red{3<= n<=4, 1<=a_{ij}<=n^2}$

对于$\red{100\%}$的数据满足， $\red{3<= n<=10, 1<=a_{ij}<=n^2}$