Ngoài việc chơi với các bảng số ~01~, Bé còn rất thích chơi với những dãy ngoặc. Hôm nay, mẹ cho Bé ~N~ dãy ngoặc. Bé muốn tạo được một dãy ngoặc đúng bằng việc nối một số dãy ngoặc lại với nhau. Bạn hãy giúp bé nhé.

Một dãy ngoặc đúng được định nghĩa theo kiểu đệ quy như sau:

• Dãy rỗng - dãy không gồm ký tự nào - là dãy ngoặc đúng.
• Nếu ~X~ là một dãy ngoặc đúng, thì ~(X)~ cũng là một dãy ngoặc đúng. Ví dụ, vì ~X = ()()~ là một dãy ngoặc đúng nên ~(()())~ cũng là một dãy ngoặc đúng.
• Nếu ~X~ và ~Y~ là hai dãy ngoặc đúng, thì ~XY~ là một dãy ngoặc đúng. Ví dụ, vì ~X = (())~ và ~Y = ()~ là các dãy ngoặc đúng, nên ~XY = (())()~ cũng là dãy ngoặc đúng.

Một số ví dụ về các dãy không phải là dãy ngoặc đúng: ~)(~, ~(()))~, ~((()~, ....

Input

• Dòng ~1~: Số nguyên dương ~N~ duy nhất
• ~N~ dòng tiếp, mỗi dòng ghi ~1~ dãy ngoặc

Output

Độ dài của dãy ngoặc lớn nhất tìm được

Giới hạn

• Trong tất cả các test, ~N \leq 1000~, tổng độ dài các dãy ngoặc trong input không quá ~10^4~
• Trong ~30\%~ test, ~N \leq 8~, tổng độ dài các dãy ngoặc không quá ~100~.

Sample Input

3
(
)
)(

Sample Output

4

Note

Bé có thể nối dãy ngoặc thứ ~1~ với thứ ~2~ tạo thành dãy ngoặc ~()~ là dãy ngoặc đúng. Bé cũng có thể nối dãy ngoặc thứ ~1~, thứ ~3~ rồi thứ ~2~, tạo thành dãy ngoặc ~()()~ là dãy ngoặc đúng.