题意翻译

有人饲养了n只猫。 猫[i]和猫[j]的友好指数为f[i,j], 猫的幸福指数是指与距离1以内的猫的友好指数的总和。 此人按照从猫[1]到猫[n]的顺序把猫配置于一维上。 (猫[i]的坐标为x[i],x[i]是满足x[1]小于x[2]……小于x[n]的实数) 求猫的幸福指数总和的最大值。

题目描述

[problemUrl]: https://atcoder.jp/contests/tdpc/tasks/tdpc_cat 入力は以下の形式で標準入力から与えられる。 > $ N $ $ f_{1,1}\ ...\ f_{1,N} $ $ ... $ $ f_{N,1}\ ...\ f_{N,N} $ 答えを一行に出力せよ。 ``` 3 0 2 3 2 0 -10 3 -10 0 ``` ``` 4 ``` ``` 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 ``` ``` 28 ```

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点

说明

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