Maximum Length Accepted by a Simple Regular Expression

This problem involves a simple regular expression defined over the alphabet \(\{x\}\) along with the symbols (, ), and | for grouping and union operations.

The expression is built using two operations:

• Concatenation: When expressions are written one after another, their accepted string is the concatenation of the parts. The maximum length is the sum of lengths.
• Union: The operator | represents union. The maximum accepted length is the maximum length among the alternatives.

Parentheses ( ) are used for grouping.

For example, given the regular expression:

((xx|xxx)x|(x|xx))xx

the longest string that can be generated is xxxxxx with length \(6\) (i.e. \(6\) consecutive x's).

inputFormat

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

You can assume the input represents a valid expression.

outputFormat

Output the maximum length of a string that the given regular expression can generate.

In other words, if the expression \(\mathcal{E}\) accepts some strings, output \(\max\{|s| : s \in \mathcal{L}(\mathcal{E})\}\), where \(\mathcal{L}(\mathcal{E})\) is the language defined by the expression.

sample

x

1