Morning Exercises

Interview

Time limit1sMemory limit1024 MB

Summary

Given a 2 x N pasture with some tree squares, find the longest run of tree-free columns and print twice its length.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

Each morning, Farmer John (FJ) leads his cows outside the barn for their morning calisthenics (fit cows give more milk). The cows must arrange themselves into two side-by-side lines of the same length. FJ has already set out a $2 \times N$ ( $1 \le N \le 100$ ) strip of pasture for the exercises. Think of this strip as composed of $2N$ grid squares. Just when he thought everything was ready, he realized that trees grow in some of these squares. Cows cannot stand on top of trees.

The cows must be grouped tightly together, so FJ cannot use other parts of the pasture. He has no choice but to split the cows into potentially multiple $2 \times K$ groups and conduct the exercises one group at a time. FJ likes conducting these exercises with larger groups of cows. Therefore, he wants to find the maximum number of cows he can take out into the pasture at once, while keeping in mind that the cows must occupy a contiguous $2 \times K$ sub-strip ( $K \le N$ ).

Input

The first line contains an integer $N$ . Each of the next $N$ lines contains two space-separated integers that describe one $1 \times 2$ strip of pasture. A square has a 1 if there is a tree in that square and a 0 if there is not.

Output

Print one integer, the number of cows that can participate in the exercise at once.

Examples1

Example 1
Input
```
7
0 0
1 0
1 1
0 0
0 0
0 0
0 1
```
Expected output
```
6
```