#P0853. 小B的传说
小B的传说
题目描述
传说,如果你参加1000场 比赛,最后会有个神秘动画彩蛋 (c)
和 都喜欢参加 的比赛。 跟 打赌,说他能参加的评级赛比 多。起初, 的初始评分是 。总共会有 场比赛,每场比赛分两种类型:
— 所有人都算评级
— 只有评分严格低于 X 的选手算评级,其他人都不算。
在不算评级的比赛中,的评分不会变化。如果参加某场评级赛前的评分是,那么对于任意一个满足的非负整数 ,他都能采取策略让赛后评分恰好变成(这里 是正整数)。注意,评分永远不会变成负数。
请帮算出,他最多能参加多少场评级赛。
输入格式
每个测试包含多个测试用例。第一行给出测试用例数量。接下来是各个测试用例的描述。
每个测试用例第一行包含四个整数: (, ) — 的初始评分、分区的评分门槛、最大评分变化量、比赛场数。 第二行是一个长度为 n 的数,只包含 "1" 和 "2",分别代表 和 的比赛。
所有测试用例中 的总和不超过 。
输出格式
对每个测试用例,输出一个整数——最多能参加的评级赛场数。
样例
4
2100 2100 5 3
222
2098 2100 5 6
111211
2115 2100 226 7
2211121
0 10 4 8
22111121
0
6
5
8
