Toda manhã Farmer John tira vacas do celeiro para exercícios (vacas saudáveis dão mais leite). Formam duas filas vizinhas de igual comprimento. Preparou faixa $2 \times N$ ($1 \le N \le 100$), com $2N$ células. Quando achou tudo pronto, notou árvores esquecidas em algumas. Vacas não podem ficar sobre árvores.

Precisam ficar juntas, não podendo usar outro pasto. Deve dividir em talvez vários grupos $2 \times [algum número]$ e exercitar um por vez. Prefere grupos grandes: ache o máximo simultâneo ocupando subfaixa contígua $2 \times K$ ($K \le N$).

Entrada

• Linha 1: inteiro $N$.
• Linhas $1..N+1$: dois inteiros com espaço descrevem faixa $1 \times 2$. 1 indica árvore, 0 ausência; exemplo esclarece.

Saída

• Linha 1: inteiro, número de vacas participantes de uma vez.

Exemplos

Entrada 1

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

Saída 1

6

Nota

Detalhes da entrada

É dada faixa $2\times7$ com quatro árvores.

Detalhes da saída

Maior subfaixa contígua sem árvores é $2\times3$, para $2\times3 = 6$ vacas.

Créditos: Percy Liang, 2004.