The annual bull racing has started and the raging bulls are finishing off to the finishing line. Jimmy decides to cross the finish line by riding on the bulls. Jimmy is at position \(0\) at the start time i.e time= \(0\).Initially the position of the bulls on a straight line track is given as an array \(P\). On the straight path, there are \(N\) lanes (one for each bull) and no bull can change the lane in between.
Also, each bull is racing with a constant speed, given by the array \(S\) (speed is in units per second ). Each bull is invisible initially and becomes visible at different times denoted by array \(ST\) i.e for a bull \(i\) it becomes visible at time \(ST_i\) at its position given by \(P_i\). The maximum time interval for which a bull can carry Jimmy is given by an array \(CT\) ( time is in seconds ).
Jimmy has to jump over to a different bull before the maximum carrying time of that bull is reached. Jumping over the next bull requires negligible time. Also, Jimmy can change the bull only if it is at same position ( although it can be on a different lane) as the current bull.
For a given destination \(K\) units apart from the initial point, help Jimmy to find minimum number of bull changes to reach the given destination. It is given that the transitions can happen only at integer time units.
Note: Jimmy can only make direct jumps from one bull to another and cannot jump on the ground at any instant. However, at initial position \(0\) he can stay for as much time as he wants.
INPUT FORMAT
- First line contains an integer \(T\) denoting the number of testcases
- First line of each testcase contains an integer \(N\), denoting the number of bulls and \(K\) denoting the final destination( distance from the initial position of Jimmy which is 0 )
- Each of the next \(4\) lines of each testcase contains \(N\) space separated integers denoting the arrays \(P\), \(S\), \(ST\), \(CT\) respectively
OUTPUT FORMAT
- Output single integer denoting the minimum number of bull changes or -1 if is not possible
CONSTRAINTS
- \(1 \leq T \leq 100\)
- \(1 \leq K \leq 1000\)
- \(1 \leq N, S_i, CT_i \leq 10\)
- \(0 \leq P_i , ST_i \le K\)
SUBTASKS
- For 10 Points : \(1 \le K \le 10\)
- For 90 Points : Original Constraints