---

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "dungeon.h"。

---

题目描述

题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T1 「던전」

哲洙和英姬在游戏中需要穿越一个地牢。地牢是一个 $N \times N$ 的网格。网格的行从上到下编号为 $0$ 到 $N-1$，列从左到右编号为 $0$ 到 $N-1$。位于第 $i$ 行，第 $j$ 列的格子记为 $(i, j)$。

穿越地牢的规则如下：

• 哲洙从地牢的左上角出发，移动到右下角。每次移动时，哲洙只能向右或向下移动到相邻的格子。
• 英姬从地牢的右上角出发，移动到左下角。每次移动时，英姬只能向左或向下移动到相邻的格子。

地牢的每个格子里都有一个物品。每个物品的价值可以是正整数、$0$ 或负整数，位于 $(i, j)$ 格子的物品价值为 $V[i][j]$。哲洙和英姬已经知道所有格子中物品的价值。穿越地牢后，哲洙和英姬会收集他们经过的所有格子的物品。如果两人都经过同一个格子，那么这个格子的物品只会被收集一次。

请编写一个程序，计算哲洙和英姬能够收集的物品价值的最大可能总和。

---

实现细节

你需要实现以下函数：

int max_item_sum(vector<vector<int>> V);

• V：大小为 $N \times N$ 的二维整数数组。对于所有 $i, j$ $(0 \leq i, j \leq N-1)$，$V[i][j]$ 是地牢中 $(i, j)$ 格子的物品价值。
• 该函数返回哲洙和英姬能够收集的物品价值的最大可能总和。

注意，提交的代码中不应包含任何输入输出操作。

---

样例 1

考虑 $N=5, V=[[-1,-1,-1,-1,-1],[-1,-1,1,-1,-1],[-1,-1,-1,-1,-1],[-1,-1,1,-1,-1],[-1,-1,-1,-1,-1]]$ 的情况。

评测程序将调用如下函数：

max_item_sum([[-1,-1,-1,-1,-1],[-1,-1,1,-1,-1],[-1,-1,-1,-1,-1],[-1,-1,1,-1,-1],[-1,-1,-1,-1,-1]]);

下图展示了地牢的情况。每个格子中的值表示该格子的物品价值。

下图左侧的蓝色格子表示哲洙经过的格子，右侧的黄色格子表示英姬经过的格子。哲洙经过的格子中物品的总价值为 $-4$，英姬经过的格子中物品的总价值也是 $-4$，两人都经过的格子中物品的总价值为 $-1$。因此，物品的总价值为 $-9$，这是可能的最大总和。

函数应返回 $-9$。

---

样例 2

考虑 $N=5, V=[[1,2,3,4,5],[2,3,4,5,1],[3,4,5,1,2],[4,5,1,2,3],[5,1,2,3,4]]$ 的情况。

评测程序将调用如下函数：

max_item_sum([[1, 2, 3, 4, 5], [2, 3, 4, 5, 1], [3, 4, 5, 1, 2], [4, 5, 1, 2, 3], [5, 1, 2, 3, 4]]);

函数应返回 $60$。

---

样例 3

考虑 $N=5, V=[[1,1,-1,-1,1],[-1,1,-1,1,1],[1,1,1,1,-1],[1,-1,-1,1,-1],[1,-1,-1,1,1]]$ 的情况。

评测程序将调用如下函数：

max_item_sum([[1, 1, -1, -1, 1], [-1, 1, -1, 1, 1], [1, 1, 1, 1, -1], [1, -1, -1, 1, -1], [1, -1, -1, 1, 1]]);

函数应返回 $15$。

---

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 1000$
• 对于所有 $i,j$ $(0 \leq i, j \leq N-1)$，$-10^5 \leq V[i][j] \leq 10^5$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	11	$N \leq 5$
2	44	$N \leq 300$
3	15	对于所有 $i,j$ $(0 \leq i, j \leq N-1)$，$V[i][j] \geq 0$
4	30	无附加限制

---

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2+i$ $(0 \leq i \leq N-1)$ 行：$V[i][0]\,V[i][1]\,\cdots\,V[i][N-1]$

示例评测程序按以下格式输出：

• 第 $1$ 行：函数 max_item_sum 返回的值

注意，示例评测程序可能与实际评测程序不同。

---