#P1011. Ranking Prediction

Ranking Prediction

Description

你和队友刚刚结束了一场 ICPC 比赛。五个小时的鏖战耗尽了你的精力,而你的队友还吃掉了你的午饭。现在你只能靠在桌子上,望着排行榜发呆。颁奖典礼尚未举行,排行榜仍处于封榜状态——这意味着你知道自己队伍整个比赛期间的所有提交时间和通过情况,但对于其他队伍,你只知道他们每次提交的时间,以及封榜之前的提交是否通过,而封榜之后的提交是否通过你一无所知。

在查看排行榜时,你注意到了某支让你格外在意的队伍。你知道他们封榜前每次提交的时间和状态,也知道封榜后每次提交的时间。你想知道他们的最终排名是否会严格高于你的队伍。为了判断这种可能性,你还想知道,他们至少需要在封榜后解出多少道题,才能使最终排名严格高于你。

在 ICPC 比赛中,罚时按如下规则计算。假设某支队伍通过了 mm 道题,编号为 11 至 mm。对于每道通过的题 ii,设首次通过的时间为 tit_i,通过该题之前的不通过提交次数为 cic_i。罚时 pp 的计算公式为:

p=∑i=1mti+20⋅cip=\sum_{i=1}^m t_i+20\cdot c_i

本题中不考虑编译错误等不计入罚时的特殊情况。

对于两支队伍 AA 和 BB,称队伍 AA 的排名严格高于队伍 BB,当且仅当 AA 通过的题数大于 BB 通过的题数,或者 AA 与 BB 通过的题数相等且 AA 的罚时小于 BB 的罚时。

Format

Input

第一行包含一个整数 TT (1≤T≤1001\le T\le 100),表示测试数据组数。

对于每组测试数据,第一行包含三个整数 n,a,bn,a,b (10≤n≤15,1≤a≤n,0≤b≤10510\le n\le 15,1\le a\le n,0\le b\le 10^5),表示比赛共有 nn 道题,你的队伍到比赛结束时通过了 aa 道题,罚时为 bb。

第二行包含一个整数 ss (0≤s≤1030\le s\le 10^3),表示你关注的那支队伍在正常比赛期间的提交次数。

接下来 ss 行,每行包含一个整数和两个字符串 t,p,vt,p,v (0≤t<3000\le t \lt 300)。表示在第 tt 分钟,该队伍对题目 pp 提交了一次,结果为 vv。保证提交按时间顺序给出(即当 tt 相同时,提交顺序即为输入给出的顺序),pp 为前 nn 个大写字母之一,v∈{ac,rj,pd}v\in \{\texttt{ac}, \texttt{rj}, \texttt{pd}\}。ac 表示该次提交通过,rj 表示该次提交不通过,pd 表示该次提交处于封榜状态,其结果未知。保证当 t<240t \lt 240 时 vv 不为 pd,当 t≥240t\ge 240 时 vv 一定为 pd。

Output

对于每组测试数据,输出一行一个整数。如果你关注的那支队伍不可能获得严格高于你队伍的最终排名,输出 −1-1;否则,输出他们至少需要在封榜后解出多少道题,才能使最终排名严格高于你。

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.