题目描述

输入一个 $n\times n$ 的矩形，每个 $a_{i,j}$ 是这个位置的价值。现在要从左上角走到右下角再返回，每个价值只被计算一次，求最大价值和。

输入格式

第一行一个整数 $n$，$1\le n\le 300$。

接下来是一个 $n\times n$ 的矩阵，矩阵元素 $|a_{i,j}| \le 1000$。

输出格式

输出一个整数表示答案。

1
5

5

2
11 14
16 12

53

3
25 16 25
12 18 19
11 13 8

136