【East!_XVI】不祥之刃

2015年4月4日1,2340

Background

卡特琳娜又要怒拿五杀了,怎么办啊?某无良设计师伊泽瑞 尔笑了笑:“基兰,断网,重赛!”

Description

卡特琳娜要从 1 到 N 依次通过这 N 个李青[小学僧/盲僧], 并最终击杀第 N+1 个李青[Dopa 僧]。对于[小学僧],卡特琳娜 可以击杀他得到一点法强和数量等同于该[小学僧]权值的金币; 对于[盲僧],如果卡特琳娜当前法强大于等于该[盲僧]的权值, 就会被该[盲僧]击杀。

现在卡特琳娜要击杀[Dopa 僧],就必须得到大于等于其权 值的法强。问卡特琳娜满足击杀[Dopa 僧]的前提下最多能得到 多少金币?

Input

第一行两个整数 N,M。M 表示[Dopa 僧]的权值。 接下来 N 行每行一个字符和一个权值。 如果是“d”,表示 student[小学僧] 如果是“p”,表示 perfect [ 盲僧 ]

Output

输出一个数如题,如果不能击杀[Dopa 僧],则输出“-1”。 Sample Input

42 d1 d2 p2 d1

Sample Output

3

Data Constraint

序号

N

特殊限制

1

0

2

[1,500]

3,4

[1,8000]

5,6

[1,500000]

暑假,全是小学僧。

7

[1,500000]

Ans == “-1”

8,9,10

[1,500000]

良心数据,无需 long long。 After Problem

鉴于伊泽瑞尔妹子太多,所以基兰把伊泽瑞尔移除了,但是 他的原画被增加了粒子特效,现在伊泽瑞尔看起来更酷炫了。

题解

出题人18357:

首先我们可以处理出到每个点时最多能取几个。 然后我们从头到尾扫一遍,然后把能取的都入优先队列,一旦超过到 该点的限制,就让最小的出队。 最后剩下的就是能取的所有点中最优集合。