Chaque matin Farmer John sort les vaches de l'étable pour la gymnastique (les vaches en forme donnent plus de lait). Elles forment deux rangées voisines de même longueur. Il a préparé une bande $2 \times N$ ($1 \le N \le 100$), soit $2N$ cases. Croyant tout prêt, il remarque les arbres oubliés dans certaines cases. Les vaches ne peuvent se tenir sur eux.

Il faut un groupe serré, les autres parties du pré sont inutilisables. Il doit donc former éventuellement plusieurs groupes $2 \times [un certain nombre]$ et les exercer un à un. Il préfère les grands groupes : trouvez le maximum de vaches simultanées occupant une sous-bande contiguë $2 \times K$ ($K \le N$).

Entrée

• Ligne 1 : entier $N$.
• Lignes $1..N+1$ : deux entiers séparés par un espace décrivent une bande $1 \times 2$. Arbre : 1 ; aucun : 0. L'exemple clarifie cela.

Sortie

• Ligne 1 : entier, nombre de vaches pouvant participer à la fois.

Exemples

Entrée 1

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

Sortie 1

6

Remarque

Détails de l'entrée

Une bande $2\times7$ avec quatre arbres est donnée.

Détails de la sortie

La plus grande sous-bande contiguë sans arbres est $2\times3$, contenant $2\times3 = 6$ vaches.

Crédits : Percy Liang, 2004.