你正在第无数次玩你最喜欢的游戏《地下室与鸽子生物》（Basements and Pigeonlike Creatures）。你对这个游戏非常熟悉，但从未花足够的时间去研究最佳策略。不过，现在不同了。游戏包含一系列特定的事件，例如与怪物战斗或从树上救下一只猫，你需要完成所有事件才能获胜。每个事件都关联着一个属性（例如力量）和一个阈值（一个正整数）。如果你的属性值达到或超过了该阈值，你就成功完成了该事件！否则，很遗憾，游戏结束，你的总分将为零。

CC BY-NC 2.5 by xkcd.com

如果你成功完成了所有事件，你的得分取决于你在这些事件中的表现。如果你的属性值恰好等于事件的阈值，你将获得 0 分，勉强通过该事件。如果你超过了阈值，你将获得等于该事件所使用的属性值的积分。

你现在处于游戏的最后阶段，但首先你有一些属性点可以用来提升你的属性值。你知道游戏最后阶段会发生哪些事件，所以剩下的工作就是确定要提升哪些属性。

输入格式

输入包含：

• 一行包含一个整数 $n$ ($1 \le n \le 10^5$) 和一个整数 $k$ ($1 \le k \le 10^9$)，分别表示属性的数量和你还可以花费的属性点数。
• $n$ 行，每行包含一个不同的属性名称，以及一个整数 $s$ ($0 \le s \le 10^9$)，表示你当前在该属性上的分数。
• 一行包含一个整数 $l$ ($1 \le l \le 10^5$)，表示事件的数量。
• $l$ 行，每行描述一个事件，包含所使用的属性名称，以及一个整数 $t$ ($0 \le t \le 10^9$)，表示该事件的阈值。

属性名称由大写英文字母 (A-Z) 组成，长度在 1 到 20 个字符之间（含边界）。

输出格式

输出你可以从这些事件中获得的最大得分。

样例

样例输入 1

2 3
STR 15
CON 12
2
STR 17
CON 14

样例输出 1

0

样例输入 2

3 7
JUMP 5
RUN 7
FLY 0
4
FLY 0
JUMP 6
RUN 10
RUN 8

样例输出 2

31