Mỗi sáng Farmer John đưa bò ra khỏi chuồng tập thể dục (bò khỏe cho nhiều sữa). Bò phải thành hai hàng cạnh nhau bằng dài. Ông chuẩn bị dải $2 \times N$ ($1 \le N \le 100$) gồm $2N$ ô. Tưởng đã xong, ông nhận ra bỏ sót cây trong vài ô. Bò không đứng trên cây.

Bò cần nhóm sát nhau nên không dùng phần đồng khác. Phải chia thành có thể nhiều nhóm $2 \times [một số nào đó]$ và tập từng nhóm. Ông thích nhóm lớn: tìm số bò tối đa cùng lúc chiếm dải con liền $2 \times K$ ($K \le N$).

Dữ liệu vào

• Dòng 1: số nguyên $N$.
• Dòng $1..N+1$: hai số nguyên cách dấu cách mô tả dải $1 \times 2$. 1 có cây, 0 không; ví dụ làm rõ.

Dữ liệu ra

• Dòng 1: số nguyên là số bò tập cùng lúc.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6

Ghi chú

Chi tiết dữ liệu vào

Dải $2\times7$ với bốn cây được cho.

Chi tiết dữ liệu ra

Dải con liền không cây lớn nhất $2\times3$, chứa $2\times3 = 6$ bò.

Tác giả: Percy Liang, 2004.