M. Катя и сломанная клавиатура
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кате задали написать эссе, но, к сожалению, она поняла, что часть клавиш у неё на ноутбуке стали не всегда нажиматься.

Опытным путём она узнала, что $$$n$$$ клавиш сломались. А именно, она для каждой сломанной клавиши $$$c_i$$$ установила число $$$x_i$$$. При нажатии в первый раз клавиша $$$c_i$$$ не срабатывает, далее $$$x_i-1$$$ раз она печатает букву, затем опять не срабатывает один раз, снова срабатывает $$$x_i - 1$$$ раз, и так далее.

Помогите Кате узнать, сколько раз ей придётся нажать на клавиши, чтобы гарантированно написать эссе.

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

В первой строке дана строка $$$s$$$ — эссе, которое Катя хотела набрать. Эссе состоит только из маленьких английских букв, длина строки не превосходит $$$100\,000$$$.

Во второй строке дано $$$n$$$ ($$$0 \le n \le 26$$$) — количество сломанных клавиш.

Следующие $$$n$$$ строк содержат $$$c_i$$$ и $$$x_i$$$, где $$$c_i$$$ —сломанная клавиша, а $$$x_i$$$ ($$$2 \le x_i \le 100$$$) —частота не срабатывания клавиши. Гарантируется, что $$$c_i$$$ — маленькая английская буква.

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

Выведите минимальное число нажатий на клавиатуре, которое гарантирует, что Катя сможет написать эссе.

Пример
Входные данные
russiaopenhighschoolteamprogrammingcontest
2
s 3
o 5
Выходные данные
46