# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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 **s _{i}** and it becomes active at

If a bus reaches a station **i** before time **t _{i}**, 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

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 **x _{i}**. The

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 ≤ 10 ^{9} ; 0 ≤ M ≤ min(D - 1, 10^{3}) ; 0 ≤ N, K ≤ 10^{3} ; 1 ≤ V ≤ 10^{3})** - 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 t_{1}, t_{2}, …, t_{M} **(1 < t _{i} ≤ 10^{9})**, where t

Next line contains M space separated **distinct** integers s_{1}, s_{2}, …, s_{M} **(1 ≤ s _{i} < D)**, where s

Next line contains N space separated integers x_{1}, x_{2}, …, x_{N} **(1 ≤ x _{i} < D)**, where x

Next line contains N space separated integers v_{1}, v_{2}, …, v_{N} **(1 ≤ v _{i} ≤ 10^{3})**, where v

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

Input | Output |
---|---|

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

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.

67% Solution Ratio

mahdi.hasnatEarliest,

mahdi.hasnatFastest, 0.3s

mahdi.hasnatLightest, 131 kB

mahdi.hasnatShortest, 1587B

Login to submit