Build String

题意翻译

# 题目大意： 你需要使用一些字符串$s_1$，$s_2$，......，$s_n$来构建字符串t，你可以执行$|t|$ （$|t|$是字符串t的长度）次操作: 1. 从字符串$s_1$，$s_2$，......，$s_n$中选择一个非空字符串； 2. 从所选字符串中选择一个字符并将其写在纸上； 3. 从所选字符串中删除所选字符。 注意：执行上述操作后，字符串$s_1$，$s_2$，......，$s_n$中的字符总数减少1。 我们认为构建出了字符串t，当且仅当写在纸上的字符按顺序连起来为t。 但是还有其他限制：对于每个字符串$s_i$，有$a_i$为允许从字符串$s_i$中删除的最大字符数。 而且，从字符串$s_i$中每个删除字符的操作都需要一些代价。对于$s_i$，从中删除1个字符需要花费i的代价。 你的任务是计算根据给定规则构建字符串t所需的最小代价。 # 输入格式 输入的第一行包含字符串t。 第二行包含一个整数n。 接下来的n行，每一行都包含一个字符串$s_i$和一个整数$a_i$（使用空格隔开），含义如题目所述。 # 输出格式 输出一个数字，为最小代价。若无解，请输出-1。 # 样例说明 ### 第一个样例： 1. 第一个字符串中取字符“b”和“z”； 2. 第二个字符串中取字符“a”，“e”和“b”。 在这种方案下，字符串t的代价是$2*1+3*2=8$。 ### 第二个样例 1. 第一个字符串中取两个字符“a”； 2. 第二个字符串中取字符“c”； 3. 第三个字符串中取两个字符“a”； 4. 第四个字符串中取两个字符“b”。 在这种方案下，字符串t的代价是$2*1+1*2+2*3+2*4=18$。 ### 第三个样例 无解，因为给定字符串中没有字符“y”。 # 数据范围 输入中的所有字符串仅由小写英文字母组成。 $1≤|t|,|s_i|≤100$，$1≤n≤100$

题目描述

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.

输入输出样例

输入样例 #1

bbaze
3
bzb 2
aeb 3
ba 10

输出样例 #1

8

输入样例 #2

abacaba
4
aba 2
bcc 1
caa 2
bbb 5

输出样例 #2

18

输入样例 #3

xyz
4
axx 8
za 1
efg 4
t 1

输出样例 #3

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