3404.卡牌游戏

Time Limits: 1000 ms Memory Limits: 262144 KB

Description

小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 受到的总伤害最大。

Input

输入的第一行包含两个整数n 和m 。

接下来n 行每行包含一个字符串和一个整数,分别表示小Y 的一张卡牌的类型(“ATK”表示攻击型,“DEF”表示防御型)和力量值。

接下来m 行每行包含一个整数,表示小X 的一张卡牌的力量值。

Output

输出一行包含一个整数,表示小Y 受到的最大总伤害。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输入1:
2 3
ATK 2000
DEF 1700
2500
2500
2500

输入2:
3 4
ATK 10
ATK 100
ATK 1000
1
11
101
1001

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输出1:
3000
【样例说明1】
第一轮,小X 选择自己的第一张卡牌和小Y 的第二张卡牌,小Y 的第二张卡牌消失。
第二轮,小X 选择自己的第二张卡牌和小Y 的第一张卡牌,小Y 的第一张卡牌消失,同时受到500 点伤害。
第三轮,小X 选择自己的第三张卡牌,此时小Y 手上已经没有卡牌,受到2500 点伤害。
小X 结束游戏,小Y 共受到3000点伤害。

输出2:
992
【样例说明2】
第一轮,小X 选择自己的第三张卡牌和小Y 的第一张卡牌,小Y 的第一张卡牌消失,同时受到91点伤害。
第二轮,小X 选择自己的第四张卡牌和小Y 的第二张卡牌,小Y 的第二张卡牌消失,同时受到901点伤害。
小X 结束游戏,小Y 共受到992点伤害。

Data Constraint

各规模均有一半数据满足小Y 只有攻击型卡牌。

对于30%的数据,1≤ n,m ≤ 6。

对于60%的数据,1≤ n,m ≤10^3。

对于100%的数据,1≤ n,m ≤10^5,力量值均为不超过10^6的非负整数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define ll long long
#define il inline
#define rgi register ll

using namespace std;

const int oo = 0x3f3f3f3f;
const ll N = 100000 + 10;

ll n, m, step, ans, minn = oo;
ll def[N], atk[N], x[N];
ll sum_def[N], sum_atk[N], sum_x[N];

il ll read()
{
rgi x = 0, f = 0, ch;
while(!isdigit(ch = getchar())) f |= ch == '-';
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}

int main()
{
m = read(),n = read();
for(rgi i = 1; i <= m; ++i)
{
char op[10];
ll val;
scanf("%s %lld", op, &val);
if(op[0] == 'A')
atk[++atk[0]] = val;
else if(op[0] == 'D')
def[++def[0]] = val;
}
for(rgi i = 1; i <= n; ++i)
x[i] = read();
sort(atk + 1, atk + atk[0] + 1);
sort(def + 1, def + def[0] + 1);
sort(x + 1, x + n + 1);
for(rgi i = 1; i <= atk[0]; ++i)
sum_atk[i] = sum_atk[i - 1] + atk[i];
for(rgi i = 1; i <= def[0]; ++i)
sum_def[i] = sum_def[i - 1] + def[i];
for(rgi i = 1; i <= n; ++i)
sum_x[i] = sum_x[i - 1] + x[i];
atk[atk[0]+1] = oo;
for(rgi i = 1; i <= n; ++i)
{
while(x[i] >= atk[step])
step++;
step--;
minn = min(minn, step + n - i);
}
ans = sum_x[n] - sum_x[n - minn] - sum_atk[minn];
if(minn >= atk[0] && n > m)
{
step = 1;
for(rgi i = 1; i <= def[0]; ++i)
{
while(def[i] >= x[step])
step++;
x[step] = 0;
}
if(step <= n - minn)
for(rgi i = 1; i <= n - minn; ++i)
ans += x[i];
}
for(rgi i = 1; i < minn; ++i)
ans = max(ans, sum_x[n] - sum_x[n - i] - sum_atk[i]);
printf("%lld", ans);
return 0;
}