#SummerP0007. 社团团建拼座位
社团团建拼座位
Description
社团团建要把 位同学排成一排合影。第 位同学和第 位同学相邻时,会产生 点快乐值。
快乐值可以理解为:"他们终于找到一个能一起吐槽食堂的人"的程度。
你需要安排所有同学的顺序,使得相邻同学产生的快乐值总和最大。
形式化地,设排列为 ,总快乐值为:
请输出最大可能的总快乐值。
Format
Input
第一行一个整数 。
接下来 行,每行 个整数,第 行第 个数为 。
保证 ,且 。
Output
输出一行一个整数,表示最大总快乐值。
Samples
4
0 1 5 2
1 0 3 4
5 3 0 6
2 4 6 0
15
Note
样例说明:
一种最优排列为 ,快乐值为 。
Related
In following contests: