Cieśla

Limit pamięci: 128 MB

Bajtazar chętnie zagrałby w warcaby, ale jego szachownica gdzieś się zawieruszyła. Udało mu się tylko znaleźć drewnianą deskę rozmiaru podzieloną na jednakowych kwadratowych pól. Każde pole jest pomalowane na biało lub czarno, ale rozkład kolorów na desce niekoniecznie odpowiada planszy do warcabów. Bajtazar postanowił zatem wykorzystać swoje ciesielskie umiejętności i za pomocą piły wyciąć szachownicę, czyli kwadrat składający się z pewnej liczby pól, w którym każde dwa pola o wspólnym boku mają różne kolory.

Nie jest jasne, czy Bajtazarowi uda się znaleźć na desce kwadrat o odpowiedniej wielkości. Dlatego stwierdził on, że wytnie z deski dwa trójkątne kawałki i sklei je razem w taki sposób, by powstała szachownica. (Kawałki muszą być rozłączne, ale można je po wycięciu w dowolny sposób obracać.) Pomóż Bajtazarowi i oblicz, jaki jest największy rozmiar szachownicy, którą może on w ten sposób wyprodukować. Poniższy obrazek przedstawia deskę rozmiaru i dwa trójkąty, które można skleić razem w szachownicę rozmiaru :

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (), które oznaczają rozmiar deski. Kolejne wierszy zawiera po liczb całkowitych: -ta liczba z -tego wiersza (, ) oznacza kolor pola leżącego na przecięciu -tej kolumny i -tego wiersza deski. Liczba 0 oznacza białe pole, a liczba 1 - pole czarne.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą największy rozmiar szachownicy, którą można uzyskać przez wycięcie z deski dwóch trójkątnych kawałków i sklejenie ich.

Przykład

Dla danych wejściowych:

4 5
1 1 0 1 1
0 1 0 1 0
1 0 1 0 0
0 0 1 1 0

3

natomiast dla danych wejściowych:

3 3
1 1 1
1 1 0
0 1 0

2

Autor zadania: Tomasz Idziaszek