Fox Ciel 正在和她的朋友 Jiro 玩纸牌游戏。
二郎有n张卡,每张都有两个属性:位置(攻击或防御)和力量。福克斯夏尔有m张卡牌,每张卡牌也都具有这两个属性。众所周知,夏尔的所有卡牌位置都是攻击。
现在是夏尔的战斗阶段,夏尔可以多次进行以下操作:
1. 选择她的一张牌 X。之前不得选择该牌。
2.如果二郎此时没有活着的牌,他将受到等于(X的力量)的伤害。否则,夏尔需要选择一张二郎的活着的牌Y,则:如果Y的位置是攻击,则(X的力量) ≥ (Y的力量)必须成立。这次攻击后,卡Y死亡,次郎受到(X的力量)-(Y的力量)的伤害。 如果Y的立场是防御,那么(X的力量) > (Y的力量)必须成立。这次攻击后,卡 Y 死亡,但次郎没有受到伤害。
夏尔可以随时结束她的战斗阶段(因此,她不能使用她的所有卡牌)。帮助狐狸计算二郎可以受到的最大伤害。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100) — Jiro 和 Ciel 拥有的牌数。
接下来的n行中的每一行都包含一个字符串位置和一个整数强度(0≤强度≤8000)——Jiro当前卡的位置和强度。位置是字符串“ATK”表示攻击,字符串“DEF”表示防御。
接下来的 m 行中的每一行都包含一个整数强度(0 ≤ 强度 ≤ 8000)——夏尔当前卡牌的强度。
输出
输出一个整数:次郎所能受到的最大伤害。
示例
输入 #1
2 3 ATK 2000 DEF 1700 2500 2500 2500
输出 #1
3000
输入 #2
3 4 ATK 10 ATK 100 ATK 1000 1 11 101 1001
输出 #2
992
输入 #3
2 4 DEF 0 ATK 0 0 0 1 1
输出 #3
1
注意
在第一个测试用例中,夏尔有 3 张强度相同的牌。最好的策略如下。首先,她使用这三张卡中的一张先攻击“ATK 2000”卡,这次攻击破坏该卡,二郎受到2500 - 2000 = 500点伤害。然后她用第二张牌破坏了“DEF 1700”牌。这次二郎没有受到伤害。现在二郎没有牌了,所以她可以使用第三张牌进行攻击,二郎受到2500点伤害。所以答案是 500 + 2500 = 3000。
在第二个测试用例中,她应该使用“1001”卡攻击“ATK 100”卡,然后使用“101”卡攻击“ATK 10”卡。现在夏尔还有牌,但她可以选择结束战斗阶段。总伤害等于 (1001 - 100) + (101 - 10) = 992。
在第三个测试用例中请注意,她可以用强度等于0的卡牌摧毁“ATK 0”卡牌,但不能用该卡牌摧毁“DEF 0”卡牌。