题目描述

Rabbit 和 Eel 在一个 $n\times m$ 的棋盘上进行博弈。每个格子包含一个数字，表示棋子进入该格子时 Rabbit 需要支付的代价。

第一回合，Rabbit 在最上面一行任选一个格子放置棋子，并支付该格子的代价。之后每回合 Rabbit 必须把棋子向左、向右或向下移动一格，并支付目标格子的代价；不能向上移动。

Rabbit 每次移动后，Eel 可以在任意若干对上下相邻的格子之间放置墙，也可以不放。墙只能阻止棋子在这两个格子之间竖直通过。已经放置的墙不会消失。Eel 必须始终保证，从棋子的当前位置仍然存在某条路径能够到达最下面一行。

当 Rabbit 第一次进入最下面一行时游戏结束。Rabbit 希望最小化总支付代价，Eel 希望最大化它。假设双方均采取最优策略，求最终总费用。

输入格式

第一行输入两个整数 $n,m$。

接下来 $n$ 行，每行输入一个长度为 $m$ 的数字字符串，第 $i$ 行第 $j$ 个字符表示该格子的费用。

输出格式

输出双方最优策略下的总费用。

数据范围

$2\le n\le 50$；$1\le m\le 50$；每个费用均为 $0$ 到 $9$ 的整数。

样例 1

2 2
12
34

6

样例 2

3 5
99999
99999
99999

99