题目描述

这是在阿尔托利亚·潘德拉贡成为英灵前的事情，她正要去拔出石中剑成为亚瑟王，在这之前她要去收集一些宝石。

宝石排列在一个 $n \times m$ 的网格中，每个网格中有一块价值为 $v_{i,j}$ 的宝石，阿尔托利亚·潘德拉贡可以选择自己的起点。

开始时刻为 $0$ 秒。以下操作，每秒按顺序执行。

1. 在第 $i$ 秒开始的时候，阿尔托利亚·潘德拉贡在方格 $(x,y)$ 上，她可以拿走 $(x, y)$ 中的宝石。
2. 在偶数秒，阿尔托利亚·潘德拉贡周围四格的宝石会消失。
3. 若阿尔托利亚·潘德拉贡第 $i$ 秒开始时在方格 $(x,y)$ 上，则在第 $i+1$ 秒可以立即移动到 $(x+1,y),(x,y+1),(x-1,y)$ 或 $(x, y- 1)$ 上，也可以停留在（$x,y)$ 上。

求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石

输入格式

第一行给出数字 $N,M$ 代表行列数 $N,M$ 均小于等于 $100$，宝石的价值不会超过 $10000$。下面 $N$ 行 $M$ 列用于描述数字矩阵。

输出格式

输出最多可以拿到多少价值宝石。

2 2
1 2
2 1

4

提示

姚金宇的原创题。