Fraction in LATEX

The LATEX publishing system is designed for typesetting complex scientific and technical documents that include numerous formulas. The initial file for LATEX is written in the TEX language and contains the document text, which incorporates special symbols and commands. These symbols and commands dictate the layout of the text, especially within mathematical formulas. A command is a sequence of Latin letters (case-sensitive) that begins with a backslash (\). For instance, the command \frac is used to represent a fraction, with the numerator positioned above the denominator. Let's explore the basic structure of the \frac command.

The \frac command requires two parameters: the numerator and the denominator. There is no need to insert a space before the command itself. After the keyword \frac, the numerator and denominator are specified. If either the numerator or the denominator consists of more than one character, they must be enclosed in curly braces. If they are a single letter or digit, they may be written without braces. When the numerator is a single character, it must be separated from \frac by at least one space. Conversely, if the denominator is a single character, it is not separated by a space from the numerator. Any number of spaces is considered equivalent to a single space. Spaces cannot separate the keyword \frac.

Here are the formal definitions for expressions in this task:

<expression> ::= <element> | <element><expression>

<element> ::= <fraction> | { <expression> } | <other mathematical element>

<fraction> ::= "\frac" <fraction body>

<fraction body> ::= <numerator><denominator>

<numerator> ::= <spaces><non-space character> | [<spaces>] "{" <expression> "}"

<denominator> ::= <non-space character> | [<spaces>] "{" <expression> "}"

<other mathematical element> ::= any sequence of printable characters that does not contain curly braces and the substring \frac

<spaces> ::= " " | " " <spaces>

<non-space character> ::= any printable character except " ", "\", "{" and "}"

In this context, the vertical bar | signifies "or," the content within square brackets may be optional, and characters in quotes represent themselves. A printable character is any character with an ASCII code from 32 (space) to 127.

For example, the expression

is written in TEX as

\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}

To display a formula in a printed document, you need to calculate its height based on the font used. The font determines two sizes: S, the height of the next character, and D, the height of the horizontal fraction line. Both S and D are given as integers. Your task is to compute the height of the formula for the provided TEX expression.

Note that if two fractions are part of the same expression, their fraction lines are aligned at the same level. However, this may not be the case if they belong to numerators or denominators of different fractions. To demonstrate this rule, consider the following examples:

\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}

\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}

Input

The first line contains positive integers S and D (1 ≤ S, D ≤ 10000). The next line provides the TEX formula description, with a maximum line length of 200 characters. The formula is guaranteed to be syntactically correct, meaning the curly braces form a valid bracket sequence, and the line contains only printable characters. All \ symbols in the line are part of command sequences (not necessarily \frac), and you can assume that all other command sequences define symbols with a height equal to S. Each fraction's numerator and denominator contain at least one character, and the entire formula contains at least one character.

Output

Output a single number representing the height of the formula.

Examples