该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小K非常喜欢数字，现在他面前有1~n的n个整数（每个数字各一个），他需要将这些数字排列，得到一个n位的整数。这个新的整数有一个属性“价值积”，即 $这个整数的大小$ 和 $各数位上数字价值之和$ 的积。小K现在获得了一个n*n的表格，上面含有每个数字放在不同位置可获得的价值，请你帮帮他求出他能得到的 $最大“价值积”$ 是多少？

对于n>=10时得到的n位整数补充解释:每一位上的数即在10进制下的自身，与n<10时的情况相同，如数列：{12,13,10}->12100+1310+10*1=1430

Input Format

第一行一个整数$n$(1<=n<=16)

第二行至第n+1行，每行有n个整数，第i+1行第j个整数a_i,j表示数字i放在第j位(从左往右数)时的价值。(1<=a_i<=4)

Output Format

一个整数，即能获得的最大价值积。

Sample

样例输入1

3
1 2 3
1 2 3
1 2 3

样例输出1

1926

样例解释1

最终得到的数字排列是 $3，2，1$ , 组合起来就是 $321$

数字3放在第1位得到价值1，数字2放在第2位得到价值2，数字1放在第3位得到价值3

故各数位价值之和为 $1+2+3=6$

最大价值积就是 $321*(1+2+3)=1926$

样例输入2

3
4 3 4
2 2 4
3 5 5

样例输出2

3120

样例解释2

最终得到的数字排列是 $3，2，1$ 组合起来就是 $321$

数字3放在第1位得到价值3，数字1放在第2位得到价值3，数字2放在第3位得到价值4

故数位价值之和为 $3+4+3=6$

最大价值积就是 $312*(3+4+3)=3120$

Hint

$1 \leq n \leq 16$

$1 \leq$ a_i,j $\leq 4$