该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$TooY0ung$ 在一个神秘的梦境中，发现自己置身于一个魔法的世界。在这个世界里，只有不断战斗，才能证明自己的强大。

$TooY0ung$ 化身为一位英勇的魔法战士，拥有强大的群伤法术。面对众多敌人，他毫不退缩，决心用智慧和力量战胜它们。

每个敌人都有一个特定的攻击力 $a_i$ 和初始血量 $h_i$。$TooY0ung$ 的攻击有一个特殊的效果：每个敌人最多只能承受 $k$ 次有效攻击。当同一敌人受到多次攻击时，从第二次攻击开始，每次攻击将只造成一半的伤害（向下取整）。

具体的战斗规则如下：

1. 在每一回合中，$TooY0ung$ 会选择一个受到伤害不足 $k$ 次且仍然存活的敌人进行攻击。如果有多个符合条件的敌人，他会选择剩余血量最低的一个；如果仍有多个，他会选择攻击力最低的一个；如果还有多个，他会选择编号最小的一个。对于当前选中的敌人，如果它是第一次受到攻击，它将受到 $u$ 点伤害；否则，它将受到 $\lfloor \frac{u}{2} \rfloor$ 点伤害（$u$ 是初始伤害值，当攻击次数增加时，伤害减半，向下取整）。

2. 在 $TooY0ung$ 攻击后，存活的敌人会反击。$TooY0ung$ 的血量将减少当前存活敌人中攻击力最大的那个敌人的攻击力值。

3. 当 $TooY0ung$ 或某个敌人的剩余血量小于等于其受到的伤害时，它就会死亡。战斗会在 $TooY0ung$ 死亡或所有敌人都死亡时结束。

现在，$TooY0ung$ 想知道，在战斗结束时，他总共击杀了多少个敌人。

输入格式

第一行输入一个数 $T$，表示组数。

接下来每组数据：

第一行输入 $n$, $u$, $k$, $hp$，前三个含义见题面，最后一个表示 $TooY0ung$ 的初始血量。

接下来输入 $n$ 行，每行两个数字 $a_i$ 和 $h_i$，含义见题面描述。

输出格式

输出 $T$ 行，表示每组数据的答案。

5
6 4 2 68
4 4
4 13
2 13
5 17
6 9
19 17
3 21 2 48
4 7
6 5
8 20
6 12 7 54
4 4
5 19
2 1
3 12
7 5
16 2
6 4 3 68
4 4
4 13
2 13
5 17
6 9
19 17
3 21 51 48
4 7
6 5
8 20

1
3
6
1
3

数据规模与约定

对于 $100\%$ 的数据，$1 \le T \le 10，1 \le n \le 10^4，1 \le u,hp,a_i,h_i \le 10^9，1 \le k \le 10^3$。