Mặc dù Bessie thấy mọi chuỗi dấu ngoặc cân bằng đều đẹp mắt, cô đặc biệt yêu thích những chuỗi mà mình gọi là cân bằng "hoàn toàn" — gồm một chuỗi các dấu (, theo sau là một chuỗi các dấu ) có cùng độ dài. Ví dụ:

(((())))

Một ngày nọ, khi đi qua chuồng, Bessie phát hiện một lưới móng ngựa kích thước \(N \times N\) trên mặt đất, trong đó mỗi móng ngựa được đặt theo hướng khiến nó trông giống ( hoặc ). Bắt đầu từ góc trên bên trái của lưới, Bessie muốn vừa đi vừa nhặt các móng ngựa sao cho chuỗi cô nhặt được cân bằng hoàn toàn. Hãy giúp cô tính độ dài của chuỗi cân bằng hoàn toàn dài nhất mà cô có thể thu được.

Ở mỗi bước, Bessie có thể di chuyển lên, xuống, sang trái hoặc sang phải. Cô chỉ có thể đi vào một ô lưới đang chứa móng ngựa; khi làm vậy, cô nhặt móng ngựa lên nên không thể quay lại chính ô đó nữa (vì ô ấy không còn móng ngựa). Ban đầu, cô nhặt móng ngựa ở góc trên bên trái của lưới. Bessie chỉ nhặt một dãy móng ngựa tạo thành một chuỗi cân bằng hoàn toàn, vì vậy cô có thể không nhặt được tất cả móng ngựa trong lưới.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\) (\(2 \le N \le 5\)).
• Các dòng \(2..N+1\): mỗi dòng chứa một chuỗi dấu ngoặc có độ dài \(N\). Tổng thể \(N\) dòng này mô tả một lưới dấu ngoặc kích thước \(N \times N\).

Dữ liệu ra

• Dòng 1 chứa độ dài của chuỗi móng ngựa cân bằng hoàn toàn dài nhất mà Bessie có thể nhặt. Nếu Bessie không thể nhặt được bất kỳ chuỗi móng ngựa cân bằng nào (chẳng hạn ô trên cùng bên trái là một dấu ngoặc đóng), hãy in ra 0.

Ví dụ

4
(())
()((
(()(
))))

8

1())
2)((
345(
876)

Nguồn

USACO 2012 November Contest, Bronze — Problem 3: Horseshoes

Tác giả đề: Brian Dean, 2012.