← 返回题目列表

Codeforces · 321/B

B. 夏尔与决斗

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

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”卡牌。