9553: 战斗爽

魔法的世界，唯有不断战斗！

魔法少女小 hua 拥有强大的群伤法术，面对多个敌人她将毫不退缩。她的攻击会让每个敌人最多承受 $k$ 次攻击，当多次攻击命中同一目标时，从第二次攻击开始将只造成一半伤害。

具体的，小 hua 和 $n$ 个敌人战斗，第 $i$ 个敌人的攻击力为 aiai，初始血量为 hihi。

每回合如下进行：

1. 小 hua 攻击一个受到伤害不足 $k$ 次的存活的敌人（若有多个则攻击剩余血量最低的一个，若仍有多个则攻击攻击力最低的一个，若还有多个则攻击编号最小的一个），若当前敌人从未受过攻击，则它受到 $u$ 点伤害，否则受到 $\lfloor u/2\rfloor$ 点伤害（下取整符号，如果 $u=2k$ 为偶数，那么 $\lfloor u/2\rfloor =k$，否则 $u=2k+1$ 为奇数，此时 $\lfloor u/2\rfloor =k$）。
2. 存活的敌人对小 hua 攻击。小 hua 的血量减少量为所有存活敌人的攻击力的最大值。
3. 当小 hua 或某个敌人受到的伤害大于等于剩余血量时，它就会死亡。当小 hua 死亡或全部敌人死亡则战斗结束。

问战斗结束时小 hua 共击杀了多少个敌人。

第一行，一个正整数 $T$ 表示测试数据的组数。

对于每组数据：

输入一行四个正整数 $n,u,k,hq$。 分别表示 敌人数量、小 hua 的攻击力、每个敌人最多受伤次数、小 hua 的初始血量。

接着输入 $n$ 行，每行 $2$ 个正整数 ai,hiai,hi 表示第 $i$ 个敌人的攻击力和初始血量。