L - 猫 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

すぬけ君は N 匹の猫を飼っている。猫 i と猫 j の仲のよさは f_{i,j} である。ある猫の幸福度は、その猫から距離 1 以内にいる猫との仲のよさの総和である。すぬけ君は、猫 1 から猫 N をこの順に一次元上に配置することにした。(猫 i の座標を x_i とすると、x_i は x_1 < x_2 < ... < x_N をみたす実数)　猫の幸福度の総和の最大値を求めよ。

Constraints

  • 1 ≤ N ≤ 1000
  • -1000 ≤ f_{i,j} ≤ 1000
  • f_{i,i} = 0
  • f_{i,j} = f_{j,i}

Input Format

入力は以下の形式で標準入力から与えられる。
N
f_{1,1} ... f_{1,N}
...
f_{N,1} ... f_{N,N}

Output Format

答えを一行に出力せよ。

Sample Input 1

3
0 2 3
2 0 -10
3 -10 0

Sample Output 1

4
たとえば、x_1 = 1, x_2 = 1.5, x_3 = 4 とすると、猫 1 と 2 の幸福度は 2 であり、猫 3 の幸福度は 0 である。

Sample Input 2

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

Sample Output 2

28