← 返回题目列表

Codeforces · 237/E

E. 构建字符串

中文机器翻译题面 查看原题

你迫切需要构建一些字符串 t。为此,您还有 n 个字符串 s1、s2、...、sn。要构建字符串 t,您可以精确地执行 |t| (|t| 是字符串 t 的长度)对这些字符串进行操作。每个操作看起来都是这样的:

1. 从字符串 s1, s2, ..., sn 中选择任意非空字符串;
2. 从所选字符串中选择任意字符并将其写在一张纸上;
3. 从所选字符串中删除所选字符。

请注意,执行上述操作后,字符串 s1, s2, ..., sn 中的字符总数减少 1。我们假设构建字符串 t,如果按照执行操作的顺序写在纸上的字符形成字符串 t。

不过,还有其他限制。对于每个字符串 si,您知道数字 ai — 允许从字符串 si 中删除的最大字符数。您还知道,每次从字符串 si 中删除字符的操作都会花费 i 卢布。也就是说,对字符串 s1 的操作是最便宜的(花费 1 卢布),对字符串 sn 的操作是最昂贵的(花费 n 卢布)。

您的任务是计算根据给定规则构建字符串 t 所需的最低金额(以卢布为单位)。将构建字符串 t 的成本视为您使用的操作的价格之和。

输入

输入的第一行包含字符串 t — 您需要构建的字符串。

第二行包含一个整数 n (1 ≤ n ≤ 100) — 允许您应用所描述操作的字符串数量。接下来的 n 行中的每一行都包含一个字符串和一个整数。第 i 行包含空格分隔的字符串 si 和整数 ai (0 ≤ ai ≤ 100)。数字ai表示可以从字符串si中删除的最大字符数。

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

输出

打印一个数字——构建字符串 t 所需的最低金额(以卢布为单位)。如果无解,则打印-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

注意

样品注释:

在第一个字符串的第一个示例中,您应该采用价格为 1 卢布的字符“b”和“z”,从第二个字符串中采用价格为 2 卢布的字符“a”、“e”和“b”。在这种情况下,字符串 t 的价格为 2·1 + 3·2 = 8。

在第一个字符串的第二个示例中,您应该从第二个字符串中取出两个字符“a”,价格为 1 卢布,从第二个字符串中取出两个字符“a”,价格为 2 卢布,从第三个字符串中取出两个字符“a”,价格为 3 卢布,从第四个字符串中取出两个字符“b”,价格为 4 卢布。在这种情况下,字符串 t 的价格为 2·1 + 1·2 + 2·3 + 2·4 = 18。

在第三个示例中,解决方案不存在,因为给定字符串中没有字符“y”。