C. Домашнее задание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этой задаче вы должны помочь Юре справиться с домашним заданием по арифметике.

Давайте назовем выражением набор переменных, цифр и других не пустых выражений заключенных в круглые скобки с расставленными между ними знаками вычитания и сложения. Обратите внимание, что выражение не может начинаться с лидирующего знака вычитания или сложения. Примеры правильных выражений: «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. Все названия переменных различные и являются строчными латинскими буквами.

1 ≤ n ≤ 105
0 ≤ m ≤ 26
 - 109 ≤ li ≤ ri ≤ 109
Выходные данные

Выведите единственное целое число — максимальное возможное значение выражения.

Примеры
Входные данные
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