#P1011. Ranking Prediction
Ranking Prediction
Description
你和队友刚刚结束了一场 ICPC 比赛。五个小时的鏖战耗尽了你的精力,而你的队友还吃掉了你的午饭。现在你只能靠在桌子上,望着排行榜发呆。颁奖典礼尚未举行,排行榜仍处于封榜状态——这意味着你知道自己队伍整个比赛期间的所有提交时间和通过情况,但对于其他队伍,你只知道他们每次提交的时间,以及封榜之前的提交是否通过,而封榜之后的提交是否通过你一无所知。
在查看排行榜时,你注意到了某支让你格外在意的队伍。你知道他们封榜前每次提交的时间和状态,也知道封榜后每次提交的时间。你想知道他们的最终排名是否会严格高于你的队伍。为了判断这种可能性,你还想知道,他们至少需要在封榜后解出多少道题,才能使最终排名严格高于你。
在 ICPC 比赛中,罚时按如下规则计算。假设某支队伍通过了 道题,编号为 至 。对于每道通过的题 ,设首次通过的时间为 ,通过该题之前的不通过提交次数为 。罚时 的计算公式为:
本题中不考虑编译错误等不计入罚时的特殊情况。
对于两支队伍 和 ,称队伍 的排名严格高于队伍 ,当且仅当 通过的题数大于 通过的题数,或者 与 通过的题数相等且 的罚时小于 的罚时。
Format
Input
第一行包含一个整数 (),表示测试数据组数。
对于每组测试数据,第一行包含三个整数 (),表示比赛共有 道题,你的队伍到比赛结束时通过了 道题,罚时为 。
第二行包含一个整数 (),表示你关注的那支队伍在正常比赛期间的提交次数。
接下来 行,每行包含一个整数和两个字符串 ()。表示在第 分钟,该队伍对题目 提交了一次,结果为 。保证提交按时间顺序给出(即当 相同时,提交顺序即为输入给出的顺序), 为前 个大写字母之一,。ac 表示该次提交通过,rj 表示该次提交不通过,pd 表示该次提交处于封榜状态,其结果未知。保证当 时 不为 pd,当 时 一定为 pd。
Output
对于每组测试数据,输出一行一个整数。如果你关注的那支队伍不可能获得严格高于你队伍的最终排名,输出 ;否则,输出他们至少需要在封榜后解出多少道题,才能使最终排名严格高于你。
Samples
1
11 6 900
13
11 C ac
34 J ac
52 D rj
61 D ac
193 A rj
207 A rj
220 G ac
245 A pd
247 A pd
262 H pd
299 A pd
299 C pd
299 K pd
2
Limitation
1s, 512 megabytes for each test case.