Задача №115237. Катя и сломанная клавиатура
Кате задали написать эссе, но, к сожалению, она поняла, что часть клавиш у неё на ноутбуке стали не всегда нажиматься.
Опытным путём она узнала, что \(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