Description

给出一个 $n\times m$ 的矩阵，每个位置 $(i,j)$ 都是一个小写字母。

定义一条路径对应的字符串为路径上字符顺次连接所形成的字符串。

请找出两条从 $(1,1)$ 到 $(n,m)$ 的路径，要求只能向下或向右走，最小化两条路径对应字符串的最长公共前缀。

Input Format

第一行两个数 $n,m$。

接下来 $n$ 行，每行 $m$ 个字符，描述整个矩阵。

Output Format

输出为一个数，即最短的最长公共前缀长度。

3 3
abe
bcx
exy

2

Hint

样例一解释

选择的两条路径分别为：

• $(1,1)\rightarrow (1,2)\rightarrow (1,3)\rightarrow (2,3)\rightarrow (3,3):$ abexy。

• $(1,1)\rightarrow (1,2)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3):$ abcxy。

它们的最长公共前缀为 $2$。可以证明没有更优的方案。

数据范围与约定

对于 $30\%$ 的数据，$1\le n,m \le 5$。

对于 $50\%$ 的数据，$1 \le n,m \le 50$。

对于另外 $20\%$ 的数据，矩阵随机生成且只含字母 a,b。

对于 $100\%$ 的数据，$1 \le n,m \le 2\times 10^3$，输入均为整数和小写字母。