Maximum Matched 'a' String Length in Simplified Regular Expressions

Given a simplified regular expression containing only (, ), |, and a, determine the maximum length of a string consisting solely of the character a that can be matched by it.

The regular expression is interpreted based on the following rules:

1. Parentheses: Evaluate expressions inside parentheses first.
2. Concatenation: When two expressions (or subexpressions defined by parentheses) appear consecutively without an operator, they are concatenated, meaning their matched lengths are added.
3. Alternation: The symbol | denotes alternation (union). Formally, an expression of the form \(E = E_1|E_2|\cdots|E_k\) means that the expression can match any one of the alternatives \(E_i\), and the maximum matched length is the maximum among them.

For example, the regular expressions (aaa)aa|aa|(a(aa)a), (aaaaa)|(aa)|aaaa, and aaaaa|aaaa|aa are equivalent and can match strings of all a's of lengths \(2\), \(4\), or \(5\).

Your task is to compute the maximum number of a's that the given regular expression can match.

inputFormat

The input consists of a single line containing a simplified regular expression made up of the characters (, ), |, and a.

outputFormat

Output an integer representing the maximum length of a string made entirely of a's that the given regular expression can match.

sample

a

1