G. Рудольф и дробный форум
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Рудольф решил создать специализированный форум математиков. Он хочет, чтобы на этом форуме сообщения составлялись в виде формул с помощью урезанного варианта системы — .

Система определяет сообщения форума как произвольную последовательность одного или более следующих элементов:

  • Идентификатор — последовательность строчных латинских букв.
  • Целое неотрицательное число — последовательность цифр.
  • Команда — последовательность строчных латинских букв, перед которой стоит символ «\».
  • Дробь — команда «\frac» предназначена для описания дроби, в которой числитель расположен над знаменателем. После ключевого слова «\frac» указываются два параметра — числитель и знаменатель. Если числитель или знаменатель имеют длину более одного символа, они заключаются в фигурные скобки. Если числитель или знаменатель записываются одной буквой или цифрой, их можно не брать в фигурные скобки. Если числитель записывается одним символом, то он отделяется от «\frac» хотя бы одним пробелом. Если знаменатель записывается одним символом, то он может не отделяться пробелом от числителя. Нельзя разделять пробелами на части ключевое слово «\frac». Числитель и знаменатель дроби сами по себе могут являться допустимыми сообщениями.
  • Функция — последовательность строчных латинских букв, после которой в фигурных скобках располагается параметр функции, представляющий собой некоторое допустимое выражение.
  • Выражение — сумма и/или разность произвольного количества допустимых элементов сообщения.

Более формально допустимые сообщения форума можно описать следующей БНФ-грамматикой:

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 символов. Гарантируется, что сообщение соответствует приведенной в условии грамматике.

Выходные данные

Выведите одно целое число — высоту сообщения.

Примеры
Входные данные
10 2
\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}
Выходные данные
34
Входные данные
10 2
no fractions here
Выходные данные
10
Входные данные
10 2
\frac {alpha} {beta+sin{2+x}}
Выходные данные
22
Входные данные
10 2
cos{\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}}