CF237E.Build String

You desperately need to build some string t. For that you've got n more strings _s_1, _s_2, ..., s__n. To build string t, you are allowed to perform exactly |t| (|t| is the length of string t) operations on these strings. Each operation looks like that:

1. choose any non-empty string from strings _s_1, _s_2, ..., s__n;
2. choose an arbitrary character from the chosen string and write it on a piece of paper;
3. remove the chosen character from the chosen string.

Note that after you perform the described operation, the total number of characters in strings _s_1, _s_2, ..., s__n decreases by 1. We are assumed to build string t, if the characters, written on the piece of paper, in the order of performed operations form string t.

There are other limitations, though. For each string s__i you know number a__i — the maximum number of characters you are allowed to delete from string s__i. You also know that each operation that results in deleting a character from string s__i, costs i rubles. That is, an operation on string _s_1 is the cheapest (it costs 1 ruble), and the operation on string s__n is the most expensive one (it costs n rubles).

Your task is to count the minimum amount of money (in rubles) you will need to build string t by the given rules. Consider the cost of building string t to be the sum of prices of the operations you use.

你急需构造某个字符串 $t$。为此，你拥有另外 $n$ 个字符串 $s_1,\ s_2,\ \dots,\ s_n$。为构造字符串 $t$，你被允许对这些字符串恰好执行 $|t|$ 次操作（其中 $|t|$ 表示字符串 $t$ 的长度）。每次操作如下：

1. 从字符串 $s_1,\ s_2,\ \dots,\ s_n$ 中任选一个非空字符串；
2. 从所选字符串中任选一个字符，并将其写在一张纸上；
3. 将该字符从所选字符串中删除。

注意：执行上述操作后，字符串 $s_1,\ s_2,\ \dots,\ s_n$ 中的字符总数将减少 1。若按操作顺序写在纸上的字符恰好构成字符串 $t$，则称字符串 $t$ 被成功构造。

然而，还存在其他限制条件。对于每个字符串 $s_i$，已知一个数 $a_i$ —— 即你最多允许从 $s_i$ 中删除的字符个数。此外，每次从字符串 $s_i$ 中删除一个字符的操作，其花费为 $i$ 卢布。也就是说，对字符串 $s_1$ 执行的操作最便宜（花费 1 卢布），而对字符串 $s_n$ 执行的操作最昂贵（花费 $n$ 卢布）。

你的任务是：在给定规则下，计算出构造字符串 $t$ 所需的最小金额（以卢布为单位）。定义构造字符串 $t$ 的总花费为所有所用操作的花费之和。

The first line of the input contains string t — the string that you need to build.

The second line contains a single integer n (1 ≤ n ≤ 100) — the number of strings to which you are allowed to apply the described operation. Each of the next n lines contains a string and an integer. The i-th line contains space-separated string s__i and integer a__i (0 ≤ a__i ≤ 100). Number a__i represents the maximum number of characters that can be deleted from string s__i.

All strings in the input only consist of lowercase English letters. All strings are non-empty. The lengths of all strings do not exceed 100 characters.

输入的第一行包含字符串 $t$ —— 你需要构造的目标字符串。

第二行包含一个整数 $n$（$1 \leq n \leq 100$）—— 表示你可以对之执行所述操作的字符串个数。接下来的 $n$ 行中，每行包含一个字符串和一个整数。第 $i$ 行包含用空格分隔的字符串 $s_i$ 和整数 $a_i$（$0 \leq a_i \leq 100$）。数字 $a_i$ 表示最多可从字符串 $s_i$ 中删除的字符个数。

输入中的所有字符串仅由小写英文字母组成，且均非空；所有字符串的长度均不超过 100 个字符。

Print a single number — the minimum money (in rubles) you need in order to build string t. If there is no solution, print -1.

输出一个整数——构建字符串 $t$ 所需的最少金额（单位：卢布）。若无法构建，输出 -1。

Notes to the samples:

In the first sample from the first string you should take characters "b" and "z" with price 1 ruble, from the second string characters "a", "e" и "b" with price 2 rubles. The price of the string t in this case is 2·1 + 3·2 = 8.

In the second sample from the first string you should take two characters "a" with price 1 ruble, from the second string character "c" with price 2 rubles, from the third string two characters "a" with price 3 rubles, from the fourth string two characters "b" with price 4 rubles. The price of the string t in this case is 2·1 + 1·2 + 2·3 + 2·4 = 18.

In the third sample the solution doesn't exist because there is no character "y" in given strings.

样例说明：

在第一个样例中，需从第一个字符串中选取字符 “b” 和 “z”，单价为 1 卢布；从第二个字符串中选取字符 “a”、“e” 和 “b”，单价为 2 卢布。此时字符串 $t$ 的总价格为 $2 \cdot 1 + 3 \cdot 2 = 8$。

在第二个样例中，需从第一个字符串中选取两个字符 “a”，单价为 1 卢布；从第二个字符串中选取字符 “c”，单价为 2 卢布；从第三个字符串中选取两个字符 “a”，单价为 3 卢布；从第四个字符串中选取两个字符 “b”，单价为 4 卢布。此时字符串 $t$ 的总价格为 $2 \cdot 1 + 1 \cdot 2 + 2 \cdot 3 + 2 \cdot 4 = 18$。

在第三个样例中，无解，因为给定的字符串中均不包含字符 “y”。