题目描述

一台巡检机器人在一天中需要依次执行若干任务。

对每组数据，机器人在时刻 $0$ 拥有满电量 $C$。第 $i$ 个任务在时刻 $t_i$ 开始，需要立即消耗 $e_i$ 单位电量。保证 $t_1<t_2<\cdots<t_n$。

机器人在不执行任务的时间里会自动充电，每经过 $1$ 个单位时间增加 $R$ 单位电量，但电量不会超过 $C$。因此，如果机器人在上一个任务时刻 $t$ 后的电量为 $b$，那么到下一个任务时刻 $t'$ 时，执行任务前的电量为

如果某个任务开始时机器人的电量小于该任务所需的 $e_i$，机器人立即停止，之后的任务不再执行。

请输出每组数据中第一个无法完成的任务编号；如果所有任务都能完成，输出 0。

输入格式

第一行一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行三个整数 $n,C,R$；
• 接下来 $n$ 行，第 $i$ 行两个整数 $t_i,e_i$。

输出格式

对每组数据输出一行一个整数，表示答案。

样例

2
4 10 2
1 6
3 7
8 10
9 2
3 5 0
1 2
2 2
3 2

0
3

数据范围

对所有数据：

• $1\le T\le 20$；
• $1\le n$，所有数据组的 $n$ 之和不超过 $2\times 10^5$；
• $0\le C,R,e_i\le 10^9$；
• $1\le t_i\le 10^9$，且严格递增。

提示：乘法与累计电量可能超过 int 范围。