AT_tdpc_cat 猫

すぬけ君养了 $N$ 只猫。猫 $i$ 和猫 $j$ 之间的亲密度为 $f_{i,j}$。某只猫的幸福度定义为与它距离不超过 1 的所有猫与它之间的亲密度之和。すぬけ君打算将猫 1 到猫 $N$ 按顺序排列在一维线上（设猫 $i$ 的坐标为 $x_i$，则 $x_i$ 满足 $x_1 < x_2 < \cdots < x_N$）。请你求出所有猫的幸福度之和的最大值。

输入的第一行为一个整数 $N$。 接下来 $N$ 行，每行有 $N$ 个整数，第 $i$ 行第 $j$ 个整数为 $f_{i,j}$。

输出一个整数，表示所有猫的幸福度之和的最大值。

### 数据范围 1. $1 \leq N \leq 1000$ 2. $-1000 \leq f_{i,j} \leq 1000$ 3. $f_{i,i} = 0$ 4. $f_{i,j} = f_{j,i}$ 由 ChatGPT 4.1 翻译