Migrated from Lutece 2410 密室逃脱

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你被困进了一个密室里，想要逃出去必须破解门上的机关。

这个机关是一个 $n$ 行 $n$ 列的矩阵，你需要从中选出 $n$ 个数，在满足其中任意两个数不在同一行或同一列的情况下，使得它们的和最大。

如果你的选择正确，门就会打开，否则这个房间将会爆炸。你能做出正确的选择吗？

Input

第一行一个整数 $n$ ($1 \le n \le 100$)，表示矩阵的行数与列数

接下来为 $n$ 行 $n$ 列的矩阵，矩阵元素为不超过 $100$ 的正整数。

Output

输出选出的数和最大为多少。

Samples

3
1 2 3
2 3 3
1 3 2

8

Resources

2020 UESTC ICPC Training for Graph