A8685 | 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.

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.

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