001 - プレスパズル

時間制限 5 秒 / メモリ制限 32 MB / 得点 10 / x 14 /


TLE
5sec
MLE
32MB
得点
10

問題

HOJ社は最近、「プレスパズル」という新しいパズルを発売しました。
プレスパズルは持っているピースを積み重ねた後、最後に2つの機械を使って上から圧力を掛けてプレスし、できる限り高さの低いタワーを作るゲームです。
このプレス機は図の様なプレスの方法をします。

図1のような7つのピースがあったとします。
図2の様に積み上げたタワーを機械1で全体をプレスすると、ピースDとGや、ピースBとGの様などこも被らない場所はプレスした際に1つになります。
逆に、ピースAとピースEは左から2番目と左から4番目がかぶっているため、この場所は1つになりません。
機械1でプレスした結果図3のようになり、この図3を今度は機械2でプレスします。
この機械は1列ずつ上からプレスしていき、開いている隙間を埋めていきます。すると図4の様になります。
図4の中で一番高いのは左から2番目と左から4番目の5なので、このタワーの高さは5となります。
ちなみに、図2はできる限り高さの低いタワーになるように積み上げた例の一つです。
もう一つ例を紹介します。

図5の様な7つのピースがあったとします。
図6の様に積み上げたタワーを機械1で全体をプレスすると、ピースFとピースGは被っている場所が無いため、1つのピースになります。ピースDとピースEは左から3番目が被っているため、一つのピースにはなりません。
ピースAとピースCは被っている場所が無いため、1つのピースになり、なおかつ、ピースAとピースCを1つにしたピースとピースBでも被っている場所が無いため、1つのピースになります。
結果的に、ピースAとピースCとピースBで一つのピースになります。
そして、機械1でプレスした結果が図7になります。
この図7を機械2でプレスすると、図8になり、左から3番目が一番高いのでこのタワーの高さは4となります。
ちなみに、図6はできる限り高さの低いタワーになるように積み上げた例の一つです。
ピースを積み上げる際、反転や縦にしてはいけません。必ず例の様に、そのままの状態で置いてください。

このパズルを買ったあなたは、パズルを組み立てる前にできる限り高さの低くなるようにピースを積んだ場合、どのくらいの高さになるのかを調べるプログラムを作ることにしました。

入力

n m
a1,1 a1,2...a1,m
a2,1 a2,2...a2,m
.
.
.
an,1 an,2...an,m

1行目に2つの整数n,mが半角空白区切りで与えられる。
nはパズルに使われるピースの数を表し、mはピースの長さを表す
2行目から2+(n-1)行目からはピースの形aiが半角空白区切りで1行ずつ与えられる。
ai,jはi番目のピースの左からj番目という意味で、ai,jが1の場合穴が開いていない、0の場合穴が開いているとする。

出力

できる限り高さの低くなるようにピースを積んだ場合のタワーの高さFを出力せよ。出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • 1 ≦ n,m ≦ 10000
  • 答えは必ず1 ≦ F ≦ nになることが保証されている

入出力例

入力例1

7 5
1 1 1 1 0
1 1 0 1 1
0 0 1 0 0
1 0 1 0 1
0 1 0 1 1
1 1 1 1 1
0 1 0 1 0

出力例1

5

解説

これは1つ目の例と一緒である。

入力例2

7 5
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1
1 1 1 0 0
0 0 1 1 1
0 1 0 1 0
1 0 1 0 0

出力例2

4

解説

これは2つ目の例と一緒である。