Co rano Farmer John wyprowadza krowy ze stodoły na ćwiczenia (zdrowe dają więcej mleka). Mają tworzyć dwa sąsiednie rzędy tej samej długości. Przygotował pas $2 \times N$ ($1 \le N \le 100$) z $2N$ pól. Gdy uznał wszystko za gotowe, zobaczył pominięte drzewa w polach. Krowy nie staną na drzewach.

Muszą być ciasno zgrupowane, inne części pastwiska odpadają. Musi podzielić na być może wiele grup $2 \times [jakaś liczba]$ i ćwiczyć kolejno. Lubi duże grupy: znajdź maksimum jednocześnie zajmujące spójny podpas $2 \times K$ ($K \le N$).

Wejście

• Wiersz 1: całkowite $N$.
• Wiersze $1..N+1$: dwie liczby całkowite ze spacją opisują pas $1 \times 2$. 1 oznacza drzewo, 0 brak; przykład wyjaśnia.

Wyjście

• Wiersz 1: całkowite, liczba krów ćwiczących naraz.

Przykład

Wejście 1

7
0 0
1 0
1 1
0 0
0 0
0 0
0 1

Wyjście 1

6

Uwagi

Szczegóły wejścia

Podano pas $2\times7$ z czterema drzewami.

Szczegóły wyjścia

Największy spójny podpas bez drzew ma $2\times3$, mieści $2\times3 = 6$ krów.

Autor: Percy Liang, 2004.