版权声明

本题版权归 CTFPC 出题组 所有。

题目背景

（小声）这一次终于用中文题目名啦！

嫦娥是一个强迫症患者，她希望月饼的美观度最大化。否则会旋转 2lf 一分钟。

所以 2lf 找到了你，希望你替 2lf 旋转两分钟。

题目描述

月饼的美观度和月饼的位置有关，第 $i$ 个月饼在第 $j$ 个位置时，会贡献 $p_{i,j}$ 的美观度，一共有 $n$ 个月饼。我们设最优摆放顺序序列为 $a$，则美观度为：

请计算出在什么排列下，美观度能最大化。

输入格式

第一行一个正整数 $n$，表示月饼个数。

第二行到第 $n+1$ 行每行 $n$ 个非负整数，第 $i$ 行第 $j$ 个数表示第 $i$ 个月饼在第 $j$ 个位置时的美观度，即 $p_{i,j}$。

输出格式

一个整数，表示美观度。

样例

5
45 5 36 3 44
41 1 4 38 45
40 21 42 50 31
18 15 4 4 28
19 16 42 16 25

197

样例解释

最优序列为 $\{1,5,4,2,3\}$。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 20$，$0 \le p_{i,j} \le 50$。