Rikka with Traffic Light

Problem Description

Rikka is now doing summer intern abroad. Every night, she walks home from school. There is a large crossroad on the shortest path, and in most times, it takes Rikka a long time to wait for the traffic light to turn to green, even though sometimes there are not any cars or pedestrians passing through in the contradict direction. To reduce the waiting time, Rikka wants to help the government reschedule the traffic light. To make things easier, Rikka does some simplification: Suppose there are $n$ pedestrians, some of them will cross the road vertically and others will cross the road horizontally. The $i$th pedestrian will arrive at the crossroad after $t_i$ seconds. The traffic light has two possible colors: green and red. The green light means pedestrians can now cross the road vertically while red means crossing the road horizontally is allowed. Initially (i.e., at time $0$), the color of the light is green, and the color of the traffic light can be changed at any moment for any times. For any pedestrian, it will take him/her $T_1$ seconds to cross the road vertically and $T_2$ seconds to cross the road horizontally. Therefore, the $i$th pedestrian can cross the road at time $w_i$ ($w_i$ can be a floating number) if and only if $w_i \geq t_i$ and one of the following two conditions is held:

1. The pedestrian wants to cross the road vertically, and at any moment in $(w_i, w_i + T_1)$, the traffic light is green.
2. The pedestrian wants to cross the road horizontally, and at any moment in $(w_i, w_i+T_2)$, the traffic light is red. Notice that several pedestrians can cross the road at the same time: they will not impact others. Now, Rikka can schedule the state of the traffic light and the time for each pedestrian to cross the road. She wants to find the optimal valid plan so that the total waiting time is minimized, i.e., $\sum_{i=1}^n \left(w_i - t_i \right)$ is minimized. Since $t_i$ can be quite large and Rikka does not have enough patience to stay there to control the traffic light, she asks you to help her calculate the answer.

Input

The first line of the input contains a single integer $T(1 \leq T \leq 200)$, the number of test cases. For each test case, the first line contains three positive integers $n,T_1,T_2(1 \leq n \leq 3000, 1 \leq T_1,T_2 \leq 10^9)$. Then $n$ lines follow, each line with two integers $k_i,t_i(k_i \in \{1,2\}, 1\leq t_i \leq 10^9)$, which describes the $i$th pedestrian: The $i$th pedestrian will arrive at the crossroad after $t_i$ seconds, and if $k_i = 1$, he/she will cross the road vertically, otherwise he/she will cross the road horizontally. The input guarantees that there are at most $5$ test cases with $n > 500$.

Output

For each test case, output a single line with a single integer, the answer. Hint In the first test case, one of the optimal plans is: Set the traffic light to green in time period $[0,2] \cup [3,4] \cup [5,6]$, and let $w=\{1,2,3,2,3,4\}$. Therefore the answer is $3$. In the second test case, one of the optimal plans is: Set the traffic light to green in time period $[0,3] \cup [5,6]$, and let $w = \{1,3,2,3,5,3\}$. Therefore the answer is $5$. In the third test case, one of the optimal plans is: Set the traffic light to green in time period $[0,4]$, and let $w=\{1,4,2,4,3,4\}$. Therefore the answer is $6$.

Sample Input

3

6 1 1

1 1

2 1

1 2

2 2

1 3

2 3

6 1 2

1 1

2 1

1 2

2 2

1 3

2 3

6 1 3

1 1

2 1

1 2

2 2

1 3

2 3

Sample Output

3

5

6

Source

2019 Multi-University Training Contest 9