Katya 被分配了一篇作文任务，但不幸的是，她发现笔记本电脑上的一些按键有时无法响应。

经过反复试验，她发现有 $n$ 个按键坏了。具体来说，对于每个坏掉的按键 $c_i$，她确定了一个数字 $x_i$。当该按键第一次被按下时，它不工作；接着它会连续正常输入该字母 $x_i - 1$ 次；然后再次不工作一次，接着又正常输入 $x_i - 1$ 次，以此类推。

请帮助 Katya 计算出她总共需要按多少次键，才能保证她能够写完这篇作文。

输入格式

第一行给出一个字符串 $s$，表示 Katya 想要输入的作文。作文仅由小写英文字母组成，且字符串长度不超过 $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$ 为小写英文字母。

输出格式

输出保证 Katya 能够写完作文所需的最少按键次数。

样例

样例输入 1

russiaopenhighschoolteamprogrammingcontest
2
s 3
o 5

样例输出 1

46