Problem Description

You are trying to create a program to optimally divide $ N $ employees, employee $1,\ \ldots,\ N$, into at most 3 groups.

For all pairs of employees $i,\ j$ $(1\ \leqq\ i\ <\ j\ \leqq\ N)$, the happiness value $ A_{i,j} $ (not necessarily positive) that arises when they are included in the same group has already been calculated by AI.

The goodness of a group division is defined as the sum of $ A_{i,j} $ for all pairs of employees $i,\ j$ that are in the same group (or $ 0 $ if no such pairs exist). Find the maximum goodness of a group division.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_{1,2} $ $ a_{1,3} $ $\ldots$ $a_{1,\ N}$ $ a_{2,3} $ $ a_{2,4} $ $\ldots$ $a_{2,\ N}$ $ : $ $ a_{N-1,N} $

Output Format

Output the maximum goodness of a group division.

Sample Input and Output

Sample Input #1

6
10 10 -10 -10 -10
10 -10 -10 -10
-10 -10 -10
10 -10
-10

Sample Output #1

40

Sample Input #2

3
1 1
1

Sample Output #2

3

Notes/Hints

Constraints

• $2\ \leqq\ N\ \leqq\ 10$
• $-1,000,000\ \leqq\ A_{i,j}\ \leqq\ 1,000,000$
• All values in the input are integers.

Sample Explanation 1

Consider creating three groups: one consisting of employees $ 1,2,3 $, another consisting of employees $ 4,5 $, and the last consisting of employee $ 6 $. In this case, the pairs of employees in the same group are $(1,2),\ (1,3),\ (2,3),\ (4,5)$, and the goodness of this group division is $A_{1,2}\ +\ A_{1,3}\ +\ A_{2,3}\ +\ A_{4,5}\ =\ 10\ +\ 10\ +\ 10\ +\ 10\ =\ 40$. This is the optimal group division.

Sample Explanation 2

It is acceptable to include everyone in the same group.

见题面 Input 部分

见题面 Output 部分