Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Mặc dù cô bò Bessie cho rằng mọi chuỗi cân bằng để thỏa mãn thẩm mỹ của ta, cô ta thích thú hơn với những chuỗi mà cô ta gọi là “tuyệt đối” cân bằng – gồm một chuỗi dấu mở ngoặc đơn ‘(‘ và được theo sau bởi một chuỗi dấu đóng ngoặc đơn ‘)’ với cùng một độ dài. Ví dụ:

(((())))

Một ngày nọ, trong lúc đi ngang qua cái chuồng, Bessie phát hiện ra một bảng gồm N x N ô có móng ngựa ở dưới đất, trong đó những móng ngưa được sắp xếp nên nó có hình dạng của dấu mở ngoặc đơn ‘(‘ hoặc dấu đóng ngoặc đơn ‘)’. Bắt đầu từ ô trái trên của bảng, Bessie muốn đi vòng để nhặt những cái móng ngựa sao cho chuỗi mà cô ta nhặt được là chuỗi tuyệt đối cân bằng. Hãy giúp cô ta đếm độ dài dài nhất của chuỗi tuyệt đối cân bằng mà cô ta có thể nhặt được.

Ở mỗi bước, Bessie có thể đi lên phía trên, dưới, trái, và phải. Cô ta chỉ có thể đi tới một ô có chứa một cái móng ngựa, và khi cô ta làm vậy, cô ta không thể trở về vị trí cũ được nữa (vị trí đó không còn móng ngựa). Cô ta bắt đầu nhặt các móng ngựa từ ô trái trên của bảng. Bessie chỉ nhặt những móng ngưạ để có thể tạo thành một chuỗi ngoặc tuyệt đối cân bằng, nên có thể cô ta không thể nhặt hết được tất cả các móng ngựa.

Input

*Dòng 1: Một số tự nhiên N (2 <= N <= 5).

*Dòng 2..N+1: mỗi dòng chứa một chuối các dấu ngoặc có độ dài là N. Tổng cộng sẽ có N dòng thể hiện N x N ô chứa dấu ngoặc đơn.

Output

*Dòng 1: Độ dài dài nhất của chuỗi ngoặc tuyệt đối cân bằng từ các móng ngựa mà Bessie có thể nhặt được. Nếu Bessie không thể nhặt được một chuỗi cân bằng (nếu vị trí trái trên là một dấu đóng ngoặc đơn), xuất ra 0.

Example

Input:
4
(())
()((
(()(
))))

Output:
8

Dãy bước mà Bessie đi để được chuỗi tuyệt đối cân bằng có độ dài là 8 được diễn tả ở dưới:

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