問題
HOJ社は最近、「プレスパズル」という新しいパズルを発売しました。
プレスパズルは持っているピースを積み重ねた後、最後に2つの機械を使って上から圧力を掛けてプレスし、できる限り高さの低いタワーを作るゲームです。
このプレス機は図の様なプレスの方法をします。
図１のような７つのピースがあったとします。
図２の様に積み上げたタワーを機械１で全体をプレスすると、ピースDとGや、ピースBとGの様などこも被らない場所はプレスした際に１つになります。
逆に、ピースAとピースEは左から2番目と左から4番目がかぶっているため、この場所は１つになりません。
機械１でプレスした結果図３のようになり、この図３を今度は機械２でプレスします。
この機械は１列ずつ上からプレスしていき、開いている隙間を埋めていきます。すると図４の様になります。
図４の中で一番高いのは左から２番目と左から４番目の５なので、このタワーの高さは５となります。
ちなみに、図２はできる限り高さの低いタワーになるように積み上げた例の一つです。
もう一つ例を紹介します。
図５の様な７つのピースがあったとします。
図６の様に積み上げたタワーを機械１で全体をプレスすると、ピースFとピースGは被っている場所が無いため、１つのピースになります。ピースDとピースEは左から3番目が被っているため、一つのピースにはなりません。
ピースAとピースCは被っている場所が無いため、１つのピースになり、なおかつ、ピースAとピースCを１つにしたピースとピースBでも被っている場所が無いため、１つのピースになります。
結果的に、ピースAとピースCとピースBで一つのピースになります。
そして、機械１でプレスした結果が図７になります。
この図７を機械２でプレスすると、図８になり、左から３番目が一番高いのでこのタワーの高さは４となります。
ちなみに、図６はできる限り高さの低いタワーになるように積み上げた例の一つです。
ピースを積み上げる際、反転や縦にしてはいけません。必ず例の様に、そのままの状態で置いてください。
このパズルを買ったあなたは、パズルを組み立てる前にできる限り高さの低くなるようにピースを積んだ場合、どのくらいの高さになるのかを調べるプログラムを作ることにしました。
入力
n m a1,1 a1,2...a1,m a2,1 a2,2...a2,m . . . an,1 an,2...an,m
１行目に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つ目の例と一緒である。