Person in Charge

• SleepingCup

Problem Description

Little D has just joined the traffic management department of a certain country. His first task is to monitor speeding vehicles on a north-south main road of length $L$. To test Little D, his supervisor first asks him to solve a simplified scenario.

This weekend, $n$ vehicles are expected on the main road. The $i$-th vehicle enters the road at a position $d_i$ from the southernmost end and drives north with an initial speed $v_i$ and acceleration $a_i$ (uniform acceleration). We only consider vehicles traveling from south to north, so $v_i > 0$, but $a_i$ can be positive, negative, or zero. A vehicle is considered to have left the main road when it reaches the northernmost end (i.e., at position $L$ from the southernmost end) or when its speed drops to $0$ (which can only happen if $a_i < 0$).

The main road is equipped with $m$ speed detectors. The $j$-th detector is located at position $p_j$ from the southernmost end. Each detector can be turned on or off. When a vehicle passes an active detector, if its instantaneous speed exceeds the speed limit $V$, the vehicle is flagged for speeding. Note that if a vehicle enters or exits the main road at a position with an active detector, the detector will also check the vehicle's speed.

The supervisor first wants to know how many of the $n$ vehicles will be flagged for speeding if all detectors are turned on.

Additionally, to save energy, the department wants to turn off some detectors. However, they do not want to miss any speeding vehicles. That is, if a vehicle is flagged for speeding when all detectors are on, it must still be flagged after some detectors are turned off. The supervisor also wants to know the maximum number of detectors that can be turned off under this condition.

Given the large value of $n$, the supervisor allows Little D to solve these problems programmatically, so Little D turns to you for help.

Definitions and formulas related to acceleration:

• Uniform acceleration means the object's acceleration remains constant during motion, i.e., the change in speed per unit time is constant.
• For a vehicle with initial speed $v_0$ and acceleration $a \neq 0$, its speed after time $t$ is $v_1 = v_0 + a \times t$, and its displacement (distance traveled) is $s = v_0 \times t + 0.5 \times a \times t^2$.
• For a vehicle with initial speed $v_0$ and acceleration $a \neq 0$, when its displacement is $s$, its instantaneous speed is $\sqrt{v_0^2 + 2 \times a \times s}$.
• For a vehicle with initial speed $v_0$ and acceleration $a \neq 0$, when its displacement is $\frac{v_1^2 - v_0^2}{2a}$, its instantaneous speed is $v_1$.

If you use floating-point calculations, be mindful of potential precision issues.

Input Format

The first line of input contains a positive integer $T$, the number of test cases.

This is followed by $T$ test cases, each formatted as follows:

The first line contains four integers $n$, $m$, $L$, $V$, representing the number of vehicles, the number of detectors, the length of the main road, and the speed limit, respectively.

The next $n$ lines:

The $i$-th line contains three integers $d_i$, $v_i$, $a_i$, describing a vehicle.

The last line contains $m$ integers $p_1$, $p_2$, $\dots$, $p_m$, describing the positions of all detectors on the road.

Output Format

For each test case: Output one line containing two integers. The first integer is the number of vehicles flagged for speeding when all detectors are on. The second integer is the maximum number of detectors that can be turned off without missing any speeding vehicles.

Samples

1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15

3 3

Sample 1 Explanation

In this test case, the main road length is $15$, and the speed limit is $3$. Detectors are located at $2$, $5$, $8$, $9$, and $15$ from the southernmost end.

• The first vehicle enters at the southernmost end and moves at a constant speed of $3$. It does not exceed the speed limit anywhere on the road.
• The second vehicle enters at position $12$ and moves at a constant speed of $4$. When it exits at the northernmost end, the detector at $15$ flags it for speeding.
• The third vehicle enters at position $1$ with an initial speed of $1$ and acceleration of $4$. After traveling $\frac{3^2 - 1^2}{2 \times 4} = 1$ unit of distance (i.e., reaching position $2$), its speed becomes $3$. It continues to speed afterward. Thus, it is flagged by all detectors except the one at $2$.
• The fourth vehicle enters at position $5$ with an initial speed of $5$ and acceleration of $-2$. After traveling $\frac{3^2 - 5^2}{2 \times (-2)}$ units of distance (i.e., reaching position $9$), its speed becomes $3$. Thus, it is flagged by the detectors at $5$ and $8$ (positions in $[5, 9)$).
• The fifth vehicle enters at position $6$ with an initial speed of $4$ and acceleration of $-4$. After traveling $\frac{3^2 - 4^2}{2 \times (-4)} = \frac{7}{8}$ units of distance (i.e., reaching position $6\frac{7}{8}$), its speed becomes $3$. Thus, it exceeds the speed limit in $[6, 6\frac{7}{8})$, but no detectors are present in this interval, so it is not flagged.

Therefore, the second, third, and fourth vehicles are flagged for speeding, so the first output number is $3$.

We can turn off the detectors at $2$, $8$, and $9$, keeping only those at $5$ and $15$. The three previously flagged vehicles are still flagged. This is the optimal solution, so the second output number is $3$.

Sample 2

See the files detect/detect2.in and detect/detect2.ans in the contest directory.

This sample satisfies $n, m \le 10$.

Sample 3

See the files detect/detect3.in and detect/detect3.ans in the contest directory.

This sample satisfies Special Property A, with the first 10 test cases satisfying $n, m \le 3000$.

Sample 4

See the files detect/detect4.in and detect/detect4.ans in the contest directory.

This sample satisfies Special Property B, with the first 10 test cases satisfying $n, m \le 3000$.

Sample 5

See the files detect/detect5.in and detect/detect5.ans in the contest directory.

This sample satisfies Special Property C, with the first 10 test cases satisfying $n, m \le 3000$.

Data Range

For all test data, the following guarantees hold:

• $1 \le T \le 20$;
• $1 \le n, m \le 10^5$, $1 \le L \le 10^6$, $1 \le V \le 10^3$;
• $0 \le d_i < L$, $1 \le v_i \le 10^3$, $|a_i| \le 10^3$;
• $0 \le p_1 < p_2 < \dots < p_m \le L$.

Special Property A: $a_i = 0$.

Special Property B: $a_i > 0$.

Special Property C: $a_i < 0$, and no vehicle exits at the northernmost end.