Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOBRACK - Dãy ngoặc

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vobrack


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.


Được gửi lên bởi:VOJ Team
Ngày:2013-12-21
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Online 14

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.