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想知道多快才能结束游戏。给定初始棋盘，请计算最少需要进行几轮消除才能使游戏结束。

Format

Input

第一行包含2个正整数n，m，中间由一个空格隔开，表示棋盘为n行m列。
接下来m行，每行包含一个长度不超过n的非空字符串，一次描述每一列从下到上的棋子，字符串只包含字符0和1，若第i个字符为0，表示该列从下往上第i个棋子为黑色，反之，若字符为1，表示棋子为白色。

Output

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

Sample 1

Input

4 3
10
1110
0100

Output

5

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

Sample 2

Input

5 2
10101
0101

Output

0

【样例2解释】
初始时就无法消除任何棋子，故答案为0.

Limitation

1s, 524288KiB for each test case.
对于30%的数据 1<=n<=10,1<=m<=5;
对于60%的数据 1<=n<=30,1<=m<=20;
对于80%的数据 1<=n<=300,1<=m<=50;
对于100%的数据 1<=n<=10,000 ,1<=m<=100;