Рудольф решил создать специализированный форум математиков. Он хочет, чтобы на этом форуме сообщения составлялись в виде формул с помощью урезанного варианта системы — .
Система определяет сообщения форума как произвольную последовательность одного или более следующих элементов:
Более формально допустимые сообщения форума можно описать следующей БНФ-грамматикой:
_Statement ::= Expression | Expression Statement_ _Expression ::= Expression «+» Element | Expression «-» Element | Element_ _Element ::= Identifier | Number | Command | Fraction | Function_ _Identifier ::= Letter | Letter Identifier_ _Number ::= Digit | Digit Number_ _Command ::= «\» Identifier_ _Fraction ::= «\__frac» Symbol Symbol |_ _. «\__frac» Symbol «{» Statement «}» |_ _. «\__frac» «{» Statement «}» Symbol |_ _. «\__frac» «{» Statement «}» «{» Statement «}» _ _Function ::= Identifier «{» Expression «}»_ _Symbol ::= Letter | Digit_ _Letter ::= «a» | «b» | «c» | ... | «z»_ _Digit ::= «0» | «1» | «2» | ... | «9»_
Иногда в тексте сообщения появляются «многоэтажные» дроби, и это портит внешний вид форума, так как сообщение не помещается в строке и «сползает» вниз. Поскольку Рудольф является ярым перфекционистом, он написал скрипт для выравнивания сообщения. Но для работы этого скрипта необходимо заранее знать высоту сообщения.
Высота сообщения зависит от используемого шрифта. Шрифт определяет размеры Hs — высоту отдельного символа и Hl — высоту горизонтальной дробной черты.
Ваша задача — помочь Рудольфу определить высоту сообщения по заданным параметрам шрифта и записи сообщения в формате .
Первая строка содержит целые числа Hs и Hl (1 ≤ Hs, Hl ≤ 104) — соответственно высоту букв шрифта и высоту дробной черты соответственно.
Вторая строка содержит описание сообщения на 'е, длина которого не превышает 1000 символов. Гарантируется, что сообщение соответствует приведенной в условии грамматике.
Выведите одно целое число — высоту сообщения.
Если две дроби в сообщении принадлежат одному выражению или двум элементам одного уровня, то их дробные черты записываются на одном уровне, а если нет (например, относятся к числителям или знаменателям различных дробей), это свойство может и не выполняться. Например:
## Входные Данные
Первая строка содержит целые числа Hs и Hl (1 ≤ Hs, Hl ≤ 104) — соответственно высоту букв шрифта и высоту дробной черты соответственно. Вторая строка содержит описание сообщения на 'е, длина которого не превышает 1000 символов. Гарантируется, что сообщение соответствует приведенной в условии грамматике.
## Выходные Данные
Выведите одно целое число — высоту сообщения.
## Примеры
Входные данные10 2_\_frac{a+b}{d+1}+_\_frac ax -_\_frac 2 {2+_\_frac{3}{y}}Выходные данные34Входные данные10 2no fractions hereВыходные данные10Входные данные10 2_\_frac {alpha} {beta+sin{2+x}}Выходные данные22Входные данные10 2cos{_\_frac{alpha}b}Выходные данные22Входные данные10 2_\_frac a {sin{a}}Выходные данные22Входные данные10 2_\_frac{a+b}{_\_frac cd}+_\_frac{_\_frac ef}{g+h}Выходные данные46Входные данные10 2_\_frac{a+b+c}{_\_frac{_\_frac de}{g+h}}+_\_frac{i+j+k}{_\_frac{l+m}{_\_frac no}}Выходные данные46
## Примечание
Если две дроби в сообщении принадлежат одному выражению или двум элементам одного уровня, то их дробные черты записываются на одном уровне, а если нет (например, относятся к числителям или знаменателям различных дробей), это свойство может и не выполняться. Например: _\__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}}_
[samples]
**Definitions**
Let $ H_s \in \mathbb{Z}^+ $ be the height of a single character.
Let $ H_l \in \mathbb{Z}^+ $ be the height of a horizontal fraction bar.
Let $ S $ be a string representing a valid statement in the given BNF grammar.
**Grammar (simplified for height computation):**
- A *Statement* is a sequence of *Expressions*.
- An *Expression* is a sequence of *Elements* connected by `+` or `-`.
- An *Element* is one of:
- *Identifier* (letter sequence),
- *Number* (digit sequence),
- *Command* (`\` + identifier),
- *Fraction* (`\frac{...}{...}` or variants),
- *Function* (identifier + `{` expression `}`).
- A *Fraction* has numerator and denominator, each a *Statement*.
**Height Rules:**
- The height of a non-fraction element is $ H_s $.
- The height of a fraction is:
$$
\text{height} = \text{height}(\text{numerator}) + H_l + \text{height}(\text{denominator})
$$
- For a sequence of elements (e.g., $ a + b + c $), the height is the **maximum** height among its elements.
- Nested fractions contribute additively: each level of nesting adds $ H_l $ and the height of the nested expression.
**Constraints**
- $ 1 \leq H_s, H_l \leq 10^4 $
- $ |S| \leq 1000 $
- $ S $ is guaranteed to be well-formed per the grammar.
**Objective**
Compute the total height of the statement $ S $, defined recursively as the maximum height of its top-level elements, with fractions contributing additive height from nesting.