你正在与同事 Sergey 一起为公司的小型台球比赛组织团建活动。然而，你们之间的沟通并不顺畅。你不确定你和 Sergey 的想法是否一致，但就你而言，这是一个进行团队建设的好机会。奖品本身并不重要，但通过团队协作可能会收获很多。你想要最大化活动的效果。

Unbalanced scales (from WikiMedia Commons)

你开始阅读一些关于团队管理的伪科学书籍，经过一番研究，你得出结论：有两种很好的团队建设方式：人们在取得辉煌胜利或惨痛失败后会感到更加紧密。这给了你一个绝妙的主意：如果你将同事分成两组，使他们的技能水平尽可能拉开差距，那么两个团队都会获得更好的凝聚力！因此，你认为让团队尽可能不平衡是最佳方案。但请务必确保两个团队的人数相等。

经过一番思考，你提出了一个很好的团队实力模型。你认为团队实力主要取决于两名球员的配合程度，即他们是否相互鼓励并弥补对方的弱点。每当两名球员 $i$ 和 $j$ 在同一个团队时，他们会使团队得分增加一个整数 $c_{i,j}$。因此，一个团队的总得分等于该团队中所有无序球员对 $i$ 和 $j$ 的 $c_{i,j}$ 之和。

输入格式

输入包含： 一行一个偶数 $n$ ($2 \le n \le 1000$)，表示球员总数。 $n$ 行，第 $i$ 行包含 $n$ 个整数 $c_{i,1}, c_{i,2}, \dots, c_{i,n}$ ($-10^6 \le c_{i,j} \le 10^6$)。

对于任意 $i$ 和 $j$，保证 $c_{i,i} = 0$ 且 $c_{i,j} = c_{j,i}$。

输出格式

输出两个人数相等的团队之间实力的最大可能差值。

样例

输入格式 1

6
0 4 -6 2 3 -3
4 0 2 -6 0 0
-6 2 0 0 2 2
2 -6 0 0 -1 5
3 0 2 -1 0 -4
-3 0 2 5 -4 0

输出格式 1

0

输入格式 2

4
0 1 2 2
1 0 8 -3
2 8 0 5
2 -3 5 0

输出格式 2

6