Ogni mattina Farmer John porta le mucche fuori dal fienile per esercizi (quelle sane danno più latte). Formano due file affiancate di uguale lunghezza. Ha preparato striscia $2 \times N$ ($1 \le N \le 100$) di $2N$ caselle. Credendo tutto pronto, nota alberi dimenticati in alcune. Non possono stare sugli alberi.

Devono essere compatte, non può usare altro pascolo. Deve dividere in forse più gruppi $2 \times [un certo numero]$ ed esercitarne uno alla volta. Preferisce grandi gruppi: trova il massimo simultaneo su sottostriscia contigua $2 \times K$ ($K \le N$).

Input

• Riga 1: intero $N$.
• Righe $1..N+1$: due interi con spazio descrivono striscia $1 \times 2$. 1 indica albero, 0 assenza; esempio chiarisce.

Output

• Riga 1: intero, numero di mucche partecipanti insieme.

Esempi

Input 1

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

Output 1

6

Nota

Dettagli dell'input

È data striscia $2\times7$ con quattro alberi.

Dettagli dell'output

La massima sottostriscia contigua senza alberi è $2\times3$, per $2\times3 = 6$ mucche.

Crediti: Percy Liang, 2004.