“糖果链”是由单个糖果组成的序列。糖果有 26 种不同的口味，分别用小写字母 $a$ 到 $z$ 表示。Margot 的店里展示着一条非常精致的糖果链。

放学后，孩子们会来找她购买糖果链的一部分。每个孩子的偏好都不同。例如，有的孩子喜欢口味为 $ababi$ 的部分，并愿意为此支付 3 欧元。另一个孩子喜欢口味为 $axsa$ 的部分，并愿意支付 5 欧元。

Margot 可以从糖果链中截取部分并卖给孩子们。当她截取一部分时，她会将糖果链剩余的左侧和右侧部分连接起来，然后可以继续提供更多的部分，或者决定停止。

相同的口味序列可以多次卖给同一个孩子（只要 Margot 能从她的糖果链中截取出多个实例）。如果 Margot 卖不掉某些糖果，她也不会扔掉它们。她在售卖时可以将糖果部分反转（例如，$axsa$ 和 $asxa$ 是等价的）。Margot 不必满足所有孩子，也不必按特定顺序为孩子们服务。

你的任务是帮助 Margot 计算她能从糖果链中获得的最大收益。

输入格式

• 第 1 行表示 Margot 的糖果链，为一个非空字符串。
• 第 2 行包含一个整数 $C$，表示孩子的数量。
• 接下来的 $C$ 行表示每个孩子的偏好，由两个项目组成，中间用空格隔开：他或她偏好的糖果部分（用非空字符串表示），以及他或她愿意支付的金额（用整数 $P_i$ 表示）。

数据范围

• Margot 的糖果链以及每个孩子的糖果部分长度均不超过 50 个糖果；
• $1 \leqslant C \leqslant 200$；
• 对于所有 $1 \leqslant i \leqslant C$，$0 \leqslant P_i \leqslant 1\,000\,000$；
• 所有字符串仅由小写字母 $a$ 到 $z$ 组成。

输出格式

一个整数：Margot 能获得的最大收益。

样例

样例输入 1

acmicpcxxxacmzacmzacmzmca
5
icpc 5
cpci 1
acm 2
acmacm 10
xxx 0

样例输出 1

21