数字填充

【问题描述】

FireDancer最近迷上了一个填数的游戏：一个n*n的正方形棋盘，要把从1到n^2的整数填入到这个棋盘的每一个格子里(随意)。玩了很多次后，FireDancer发现了很多有趣的性质，他现在想考考你。他希望你得到一种棋盘的填法，使得任意相邻的两个格子里的数相加的最大值最小。这里的相邻指的是四个方向上的有公共边的相邻，而不是八个方向上的相邻。

【输入文件】

一个整数n(2<=n<=50)。(30％的数据n<=10)

【输出文件】

一个整数，为最小的那个值。

【输入样例】

2

【输出样例】

6

【样例说明】

一种最优填数方案为

1 4

3 2

此时，所有相邻的格子中4+2的和最大，为6。

若按以下方法填数

1 3

2 4

则，4+3的和最大，为7，没有6来得优。