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.

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.

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.