No Need for Speed

shoumo 16th December Programming...
Limits 1s, 512 MB

Mr. Baker always wanted to be a race car driver. But failing to reach his dream goal, he started his career as a bus driver. Yet he was still a race car driver inside. So, he is determined to reach the destination before any of his rivals do.

At the start of Baker's run (at 1st second), he is at point 1. The destination is at point D. In the path, there are M bus stations, which can be either active or inactive. Initially, all bus stations are inactive. A bus station becomes active when a station master reaches the station. And then that station remains active forever. The i-th bus station (1 ≤ i ≤ M) is located at point si and it becomes active at ti-th second. There can be at most one station at one point.

If a bus reaches a station i before time ti, then it will stop at the station but won't have to wait before continuing its journey. On the contrary, if the station is active when a bus reaches, then the bus has to wait K seconds before it can continue.

Every driver drives at constant speed (the constant speed can vary from driver to driver). So, if a driver having a speed of V units per second is at point X at i-th second, then he will be at the point X + V at i+1-th second. This still has a counter case. If there is a station (active or inactive) or the destination D at point P between X and X + V (X < P < X+V), it will reach point P instead of X + V at i+1-th second.

There are N rival bus drivers in the scene, and Baker wants to beat them all. At the start of Baker's journey (when he is at point 1), the i-th opponent bus (1 ≤ i ≤ N) is at point xi. The i-th opponent bus has a constant speed vi.

Baker wants to reach destination D before anyone else does, but it's possible that he won't be able to beat them with speed. So he has a backup master plan. He has put bombs inside each of the rival buses. Activating the bomb of a bus will ensure that the bus will never reach the destination. But as activating bomb is an expensive task, he wants to minimize the number of bombs to activate yet get a guaranteed win.

Determine the minimum number of bombs Baker has to activate so that he can reach the destination before any of his rivals.


The first line contains an integer T (1≤T≤100) - denoting the number of test cases. For each test case:

First line contains 5 space separated integers D, M, N, K, V (1 < D ≤ 109 ; 0 ≤ M ≤ min(D - 1, 103) ; 0 ≤ N, K ≤ 103 ; 1 ≤ V ≤ 103) - denoting the destination point, number of bus stations, number of rivals, station waiting time and Baker's constant speed respectively.

Next line contains M space separated integers t1, t2, …, tM (1 < ti ≤ 109), where ti denotes the arrival time of i-th station's station master.

Next line contains M space separated distinct integers s1, s2, …, sM (1 ≤ si < D), where si denotes the location point of i-th station.

Next line contains N space separated integers x1, x2, …, xN (1 ≤ xi < D), where xi denotes the initial position of i-th rival bus.

Next line contains N space separated integers v1, v2, …, vN (1 ≤ vi ≤ 103), where vi denotes the speed of i-th rival bus.


For each test case, print a single integer - the minimum number of bombs to be activated.


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


In the 1st Test Case, Baker will reach the destination at 5th second. The only rival would reach after Baker (at 6th second), so Baker won't have to activate any bomb.

Baker's journey starts at 1st second.

Overtaking another bus will not require any extra time or stoppage.

To win, Baker's destination reaching time has to be strictly less than any of his rivals.


Login to submit.


67% Solution Ratio
mahdi.hasnatEarliest, Dec '19
mahdi.hasnatFastest, 0.3s
mahdi.hasnatLightest, 131 kB
mahdi.hasnatShortest, 1587B
Toph uses cookies. By continuing you agree to our Cookie Policy.