G. No Speeding
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The English statement was translated by AI and may be slightly different from the original Chinese statement. Please refer to the Chinese statement if you have any questions.

Given a road of length $$$l$$$ kilometers. The road is divided into $$$n$$$ segments, each with its own speed limit. The $$$i$$$-th segment starts at distance $$$a_{i-1}$$$ kilometers from the road's start, ends at distance $$$a_i$$$ kilometers from the road's start, and has a speed limit of $$$v_i$$$ kilometers per hour.

Bob drove through the entire road. There are $$$m$$$ cameras on the road; the $$$i$$$-th camera is located at position $$$x_i$$$ kilometers from the road's start, and recorded Bob passing it at time $$$t_i$$$ hours after Bob departed from the start. Bob finally took $$$t_{end}$$$ hours to reach the end of the road.

Cameras themselves do not measure speed, but by combining Bob's passing times at multiple cameras, the traffic police may deduce that Bob must have sped on some segments. Suppose there are two cameras at positions $$$x_a$$$ and $$$x_b$$$. If driving from $$$x_a$$$ to $$$x_b$$$ while always traveling at the maximum allowed speed takes $$$t_0$$$ hours, and $$$t_b - t_a \lt t_0$$$, then Bob must have sped on some part of the road between them. (Ignore time spent accelerating or decelerating.)

Now Bob wants to know the minimum number of camera records that must be removed so that the police cannot deduce that Bob definitely sped on any segment. Note: the records at the road's start and end cannot be removed; the police always know when Bob entered and left the road.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^4$$$). The description of the test cases follows.

The first line of each test case contains four integers $$$n$$$, $$$m$$$, $$$l$$$ and $$$t_{end}$$$ ($$$1 \leq n, m \leq 2 \times 10^5$$$, $$$2 \leq l \leq 10^9$$$, $$$2 \leq t_{end} \leq 10^9$$$), denoting the number of speed-limit segments, the number of cameras, the total length of the road, and the total time Bob took to pass the road, respectively.

The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \lt a_i \lt l$$$), representing the boundaries of the segments. In particular, $$$a_0=0$$$ and $$$a_n=l$$$ always hold. When $$$n=1$$$, this line is empty.

The third line contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$v_i \in \{5, 10, 15, 20, 25, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120\}$$$), representing the speed limit of each segment.

The next $$$m$$$ lines each contain two integers $$$x_i$$$ and $$$t_i$$$ ($$$0 \lt x_i \lt l$$$, $$$0 \lt t_i \lt t_{end}$$$), representing the position of the $$$i$$$-th camera and the time Bob passed it. It is guaranteed that $$$x_1 \lt x_2 \lt \dots \lt x_m$$$ and $$$t_1 \lt t_2 \lt \dots \lt t_m$$$. For each test file, it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output a single integer on one line — the minimum number of camera records that must be removed so that the police cannot deduce that Bob definitely sped. If the police will definitely find that Bob sped regardless, output "-1".

Examples
Input
4
1 1 60 2

30
20 1
1 1 60 2

30
30 1
1 1 60 2

30
40 1
1 1 120 2

30
60 1
Output
1
0
1
-1
Input
3
5 5 949 953
359 506 602 861
110 110 10 40 20
38 80
327 245
790 333
861 455
921 915
5 5 615 8
113 193 206 350
60 100 80 25 60
3 3
285 4
318 5
348 6
402 7
5 5 824 179
51 354 656 674
60 15 90 20 5
479 4
482 21
573 22
679 78
730 97
Output
0
-1
3
Note

Speeding is illegal, dangerous, and subject to legal penalties. This problem is a contest programming exercise and describes a fictional scenario; do not attempt to evade traffic surveillance in real life. Also do not attempt to tamper with or delete camera records, as that may constitute serious criminal offenses such as damaging computer information systems. Please program responsibly and prioritize safety.