[ABC358] G - AtCoder Tour

G - AtCoder Tour

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 550 分

题面

AtCoder Land 用有 行 列的网格表示。记 为第 行、第 列的单元格。

高桥从单元格 开始，重复以下操作 次：

• 他可以留在当前单元格，或者移动到相邻的单元格。完成这一动作后，如果他在单元格 ，他将获得快乐值 。

求他能够获得的最大总快乐值。

这里，单元格 被认为与单元格 相邻，当且仅当 。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入中以以下格式给出输入：

输出

输出答案。

---

输入样例 1

2 3 3
1 2
2 1 2
3 4 5

输出样例 1

14

高桥可以通过以下行动获得总快乐值 ：

• 初始时，他在 。
• 他移动到单元格 。然后，他获得快乐值 。
• 他移动到单元格 。然后，他获得快乐值 。
• 他停留在单元格 。然后，他获得快乐值 。

他无法获得大于 的总快乐值，因此输出 。

---

输入样例 2

2 2 1000000000
2 1
100 100
100 99

输出样例 2

100000000000