В этой задаче вы должны помочь Юре справиться с домашним заданием по арифметике.
Давайте назовем выражением набор переменных, цифр и других не пустых выражений заключенных в круглые скобки с расставленными между ними знаками вычитания и сложения. Обратите внимание, что выражение не может начинаться с лидирующего знака вычитания или сложения. Примеры правильных выражений: «2+2», «(b-((a)+7))», «(a-4)+(7+a)-f-3». Примеры неправильных: «(2+2», «-a+b», «-(2+a)», «()».
К сожалению Юра не помнит точных значений переменных, но зато он знает для каждой переменной отрезок на котором она могла принимать значения. Юра уверен, что если он назначит переменным значения так, что значение выражения будет максимальным возможным, то его домашнюю работу примут.
Первая строка содержит два целых числа n и m — длина выражения и количество различных переменных в выражении.
Вторая строка содержит строку a длины n — выражение из домашнего задания Юры. Выражение будет состоять только из цифр и переменных (строчных букв латинского алфавита) описанных далее, а также операций сложения («+»), вычитания («-») и круглых скобок («(» и «)»). Все числа в выражении однозначные.
Следующие m строк будут в следующем формате: "ci li ri", где ci — название переменной, а li и ri — левая и правая граница возможных принимаемых значений переменной ci. Все названия переменных различные и являются строчными латинскими буквами.
Выведите единственное целое число — максимальное возможное значение выражения.
3 2
a-b
a 2 3
b -5 5
8
19 3
y+((y+z)+(y-x))+(z)
x 0 7
y 0 8
z 0 9
42
