Description

Full regular expressions are too complex. Here, we only consider regular expressions composed of (, ), |, and a. The operations follow the rules below:

1. When there are parentheses, we always evaluate the part inside the parentheses first.
2. When two strings (or substrings defined by parentheses) have no symbol between them, we concatenate them as a whole.
3. | is the OR operator, meaning you can choose either string on its two sides. If there are multiple OR operators at the same level, it can be viewed as choosing any one of the strings separated by these OR operators.

For example, (aaa)aa|aa|(a(aa)a), (aaaaa)|(aa)|aaaa, and aaaaa|aaaa|aa are equivalent. They all match all-a strings of length $2,4$ or $5$.

Given a simplified regular expression, write a program to compute the maximum length of an all-a string it can match.

Input Format

One line containing a valid simplified regular expression.

Output Format

One line containing an integer, which is the maximum length of an all-a string that can be matched.

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

5

((a|aaa)|aa)|a

3

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

7

Hint

[Constraints]

For $20\%$ of the testdata, the expression length does not exceed $100$, and there are no parentheses.

For $40\%$ of the testdata, the expression length does not exceed $100$.

For $70\%$ of the testdata, the expression length does not exceed $2 \times 10^3$.

For $100\%$ of the testdata, the expression length does not exceed $10^5$.

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

Translated by ChatGPT 5