2922: 卡牌游戏
题目描述
小 X 为了展示自己高超的游戏技巧,在某一天兴致勃勃地找小 Y 玩起了一
种卡牌游戏。每张卡牌有类型(攻击或防御)和力量值两个信息。
小 Y 有 n 张卡牌,小 X 有 m 张卡牌。已知小 X 的卡牌全是攻击型的。
游戏的每一轮都由小 X 进行操作,首先从自己手上选择一张没有使用过的
卡牌 X。如果小 Y 手上没有卡牌,受到的伤害为 X 的力量值,否则小 X 要从小 Y
的手上选择一张卡牌 Y。若 Y 是攻击型(当 X 的力量值不小于 Y 的力量值时才
可选择) ,此轮结束后Y消失,小Y受到的伤害为X的力量值与Y的力量值的差;
若Y是防御型(当X的力量值大于Y的力量值时才可选择),此轮结束后Y消失,
小 Y 不受到伤害。
小 X 可以随时结束自己的操作(卡牌不一定要用完)。希望聪明的你帮助他
进行操作,使得小 Y 受到的总伤害最大。
输入
输入的第一行包含两个整数 n 和 m。
接下来n行,每行包含一个字符串和一个整数,分别表示小Y的一张卡牌的
类型(“ATK”表示攻击型,“DEF”表示防御型)和力量值。
接下来 m 行,每行包含一个整数,表示小 X 的一张卡牌的力量值。
输出
输出一行包含一个整数,表示小 Y 受到的最大总伤害。
样例输入 复制
2 3
ATK 2000
DEF 1700
2500
2500
2500样例输出 复制
3000提示
【样例说明 1】
第一轮,小X选择自己的第一张卡牌和小Y的第二张卡牌,小Y的第二张卡牌
消失。
第二轮,小X选择自己的第二张卡牌和小Y的第一张卡牌,小Y的第一张卡
牌消失,同时受到 500 点伤害。
第三轮,小 X 选择自己的第三张卡牌,此时小 Y 手上已经没有卡牌,受到
2500 点伤害。
小 X 结束游戏,小 Y 共受到 3000 点伤害。
【样例输入 2】
3 4
ATK 10
ATK 100
ATK 1000
1
11
101
1001
【样例输出 2】
992
【样例说明 2】
第一轮,小X选择自己的第三张卡牌和小Y的第一张卡牌,小Y的第一张卡
牌消失,同时受到 91 点伤害。
第二轮,小X选择自己的第四张卡牌和小Y的第二张卡牌,小Y的第二张卡
牌消失,同时受到 901 点伤害。
小 X 结束游戏,小 Y 共受到 992 点伤害。
【数据规模和约定】
各规模均有一半数据满足小 Y 只有攻击型卡牌。
对于 30%的数据,1≤n,m≤ 6。
对于 60%的数据,1≤n,m≤10^3。
对于 100%的数据,1≤n,m≤10^5 ,力量值均为不超过 10^6的非负整数。