Problem Background

To solve various string matching problems, regular expressions are a powerful tool. Regular expressions define a symbolic system that can represent the properties of the strings to be searched. For example, a|aa can match a or aa, and (a|b)c can match ac or bc.

Problem Description

Complete regular expressions are too complex, so here we only consider regular expressions consisting of (, ), |, and a. The operations follow these rules:

1. When there are parentheses, we always evaluate the parts inside the parentheses first.
2. When two strings (or substrings defined by parentheses) are separated by no symbols, we always concatenate them into a single unit.
3. | is the OR operator, indicating that either side of the string can be chosen. If there are multiple OR operators at the same level, they can be considered as choosing one from the several strings separated by these OR operators.

For example, (aaa)aa|aa|(a(aa)a), (aaaaa)|(aa)|aaaa, and aaaaa|aaaa|aa are equivalent, and they all can match a string of as with lengths 2, 4, or 5.

Given a simplified regular expression, write a program to calculate the maximum length of a string of as that it can match.

Input Format

Input consists of a single line containing a valid simplified regular expression.

Output Format

Output a single integer representing the maximum length of a string of as that the expression can match.

Sample Input and Output

Sample Input #1

(aaa)aa|aa|(a(aa)a)

Sample Output #1

5

Sample Input #2

((a|aaa)|aa)|a

Sample Output #2

3

Sample Input #3

(a(aa|aaa)a|(a|aa))aa

Sample Output #3

7

Notes

[Data Range]

• For 20% of the data, the expression length does not exceed 100, and there are no parentheses.
• For 40% of the data, the expression length does not exceed 100.
• For 70% of the data, the expression length does not exceed \(2 \times 10^3\).
• For 100% of the data, the expression length does not exceed \(10^5\).

The expression is guaranteed to be valid (i.e., both sides of | and the contents inside parentheses are non-empty strings).

见题面 Input 部分

见题面 Output 部分