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: choose any non-empty string from strings s 1 , s 2 , ..., s n ; choose an arbitrary character from the chosen string and write it on a piece of paper; 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 — th