Description

小 B 设计了一种新型消棋子游戏。游戏在一个 n 行 m 列的棋盘上进行。棋盘的每个格子，要么是空，要么是黑色或白色的棋子。

游戏开始时，每一列都有一些棋子，并且所有棋子位于该列的最下方（也就是说，不在最后一行的棋子下方都有棋子）。每一轮，玩家可以选择一个棋子 A，然后将所有和棋子 A 在同一列的同一颜色连续段的棋子 B 全部消除（不包括 A 本身）。所谓 A 和B 在同一颜色连续段即 A 和 B 颜色相同，且该列在 A 和 B 之间棋子均与 A 色。若消除了至少一个棋子，那么消除成功，之后棋子 A 本身将反色（黑色变白色，白色变黑色），接着所有棋子向下掉落直到棋子落到最下方为止（棋子的相对顺序不变）；反之，如果没有棋子被消除，那么消除失败，棋盘不会有任何变化。

以下是一个 $n = 4$，$m = 4$ 的一个实例。初始棋盘为左图，第 $1$ 轮选择第 $2$ 列从下往上第 $2$ 个棋子消除时，该棋子上方和下方一共 $2$ 个棋子被消除，该棋子本身由白色变成黑色，之后棋子下落，如中图。第 $2$ 轮选择第 $3$ 列从下往上第 $4$ 个棋子消除时，该棋子下方 $1$ 个棋子被消除（注意该列最下方的黑棋子不会被消除），该棋子本身由黑色变成白色，之后棋子下落，如右图。

当所有棋子无法被消除时，游戏结束。作为游戏设计者，小 B 想知道多快才能结束游戏。给定初始棋盘，请计算最少需要进行几轮消除才能使游戏结束。

Input Format

从文件 eliminate.in 中读入数据。

第一行包含两个正整数 $n, m$，中间由一个空格隔开，表示棋盘为 $n$ 行 $m$ 列。

接下来 $m$ 行，每行包含一个长度不超过 $n$ 的非空字符串，依次描述每一列从下到上的棋子，字符串只含字符 $0$ 和 $1$，若第 $i$ 个字符为 $0$，表示该列从下往上第 $i$ 个棋子为黑色，反之，若字符为 $1$，表示棋子为白色。

Output Format

输出到文件 eliminate.out 中。

输出仅一行，包含一个整数，表示使游戏结束的最少消除轮数。

Sample

样例输入1

4 3
10
1110
0100

样例输出1

5

样例1解释

至少需要 $5$ 轮消除，一种方案为依次选择第 $2$ 列从下往上第 $2$ 个棋子、第 $3$ 列从下往上第 $4$ 个棋子、第 $2$ 列从下往上第 $1$ 个棋子、第 $3$ 列从下往上第 $2$ 个棋子、第 $3$列从下往上第 $2$ 个棋子。注意最后两轮的消除是不一样的。

样例输入2

5 2
10101
0101

样例输出1

0

样例2解释

初始时就无法消除任何棋子，故答案为 $0$。

样例3

见选手目录下的 eliminate/eliminate3.in 与 eliminate/eliminate3.ans。

Hint

对于 $30\%$ 的数据， $1 \le n \le 10$， $1 \le m \le 5$；

对于 $60\%$ 的数据， $1 \le n \le 30$， $1 \le m \le 20$；

对于 $80\%$ 的数据， $1 \le n \le 300$， $1 \le m \le 50$；

对于 $100\%$ 的数据， $1 \le n \le 10000$， $1 \le m \le 100$。