Giải bài trực tuyến

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

Chấm điểm

• Trong quá trình thi, bài của bạn sẽ chỉ được chấm với một test duy nhất là test đề bài.

Giới hạn

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

Example

Input:
3
(
)
)(

Output:
4

Giải thích

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.