存在一个大小为 $N \times M$ 的网格。第 $i$ 行第 $j$ 列的单元格包含一个非负整数 $a_{ij}$。（$1 \le i \le N$；$1 \le j \le M$）

每一轮，Minji 执行以下操作：

1. Minji 选择两个水平或垂直相邻的网格单元格。这两个单元格中至少有一个必须包含正整数。
2. Minji 将每个选定单元格中的数字减少 $1$。然而，如果某个单元格包含 $0$，她不会减少该数字。

当每个单元格都包含 $0$ 时，游戏结束。Minji 希望尽可能长时间地进行这个游戏。求在 Minji 采取最优策略时，游戏最多可以持续的轮数。

输入格式

输入的第一行包含两个空格分隔的正整数 $N$ 和 $M$。（$2 \le N, M \le 1\,000$）

接下来有 $N$ 行。其中第 $i$ 行包含 $M$ 个空格分隔的整数 $a_{i1}, a_{i2}, \cdots, a_{iM}$。（$0 \le a_{ij} \le 10^9$）

输出格式

在第一行中，输出游戏最多可以持续的轮数。

样例

输入样例 1

2 2
0 1
0 0

输出样例 1

1

输入样例 2

2 2
1 0
1 1

输出样例 2

3