D-Dahno Dahno_上海理工大学第二届“联想杯”全国程序设计邀请赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

There are $n$ items. Setsuna wants you to divide items into two sets, set $A$ and set $B$ , and neither set can be empty.

For some mysterious reasons, when item $i$ and item $j$ are in the same set, they will produce $v_{i,j}+v_{j,i}$ power.

Thus, the total power will be
$\sum_{i \in A}\sum_{j \in A} v_{i,j}+\sum_{i \in B}\sum_{j \in B} v_{i,j}$
You should find the possible maximum power.

The first line contains one integers $n$ ( $2 \leq n \leq 500$ ).

The $i$ -th line of the following n lines contains n integers $v_{i,j}(0 \leq v_{i,j} \leq 10^9)$ .

It is guaranteed that $v_{i,i}=0$ and $v_{i,j}=v_{j,i}$ .

Output the possible maximum power.

示例1

复制

复制