题目描述

你正在第无数次游玩自己最喜欢的游戏 Basements and Pigeonlike Creatures。游戏由一系列事件组成，例如与怪物战斗，或把猫从树上救下来。

每个事件都对应一种属性（例如力量）和一个非负整数门槛。若你在该属性上的数值不低于门槛，就能通过该事件；否则游戏立即结束，总得分为 $0$。

若成功通过全部事件，每个事件的得分按以下规则计算：

• 若所用属性值恰好等于该事件的门槛，则该事件得 $0$ 分；
• 若所用属性值严格大于门槛，则该事件的得分等于该属性值。

你即将进入游戏的最后阶段。在此之前，你还有 $k$ 个属性点可以分配。每个属性点可以使任意一种属性增加 $1$。你已经知道最后阶段会依次出现哪些事件。

请计算你最多可以获得多少分。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示属性种类数和仍可分配的属性点数。

接下来 $n$ 行，每行包含一个属性名和一个整数 $s$，表示该属性当前的数值。所有属性名互不相同。

随后一行包含一个整数 $l$，表示事件数量。

接下来 $l$ 行，每行包含一个属性名和一个整数 $t$，表示该事件使用的属性及其门槛。

属性名仅由大写英文字母 A 到 Z 组成，长度为 $1$ 到 $20$。

输出格式

输出一个整数，表示能够获得的最大总分。

数据范围

样例 1

输入

2 3
STR 15
CON 12
2
STR 17
CON 14

输出

0

样例 2

输入

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

输出

31