There are N shops present on number line, where each shop is located at x[ith] coordinate and has toys[ith] number of toys in it.
You are present at point P initially and move at most k steps.
Whenever you reach a shop, you get all the toys present in that shop.

Task
Determine the maximum toys you can gather after moving at most k steps.
Notes
* You can change your direction in between
* No shop is present at the initial point.
* No two shops can have the same coordinates.
* You cannot buy more from a shop you already visited

Example 1
* N=3
* P=0
* K=9
* x=[-9,-7,1]
* toys=[9,1,10]

Approach
* Since you start at coordinate 0 and you can only move 9 steps, you are only left with two good choices. Either you move to the left till -9 or first move to the right till 1 and then reverse the direction to go till -7. You cannot go to -9 in latter choice as your steps are exhausted [0 -> 1(1 steps), 1 -> -7(8 steps)]
* If you move to -9 from 0, you collect (1+9)=10 toys
* If you move from 0 to 1(1 step) and then to -7(8 steps), you collect (1+10)=11 toys

Hence in at most 9 steps you can get a maximum of 11 toys.

Example 2
* N = 4
* P = 0
* K = 4
* x = [-5,-1,2,5]
* toys = [10,2,3,4]

Approach
* Initially you start at coordinate 0 and can move at most 4 steps. It can be noticed that you cannot reach -5 or 5. So the optimal move should be reaching the shops at -1 and 2.
* If you start moving to shop at coordinate 2, you will use 2 steps, then to -1 will take 3 steps making total of 5 steps, hence you could not take 3 toys at the shop present on coordinate 2.
* If you first started toward shop at -1, it would take 1 step and then shop at 2 would take 3 steps making total of 4 steps, hence you are able to take (2+3) = 5 toys.
Hence the maximum number of toys can take is 5.

Example 3
* N = 10
* P = -19
* K = 35
* x = [-20,-11,-2,1,2,8,9,10,15,16]
* toys=[87,54,81,45,100,26,93,17,24,77]
Output: 527

Example 4
* N = 10
* P = 9
* K = 15
* x = [-28,-6,-1,1,7,11,12,16,17,20]
* toys=[77,50,73,86,57,50,6,27,91,76]
Output: 307

Constraints
1 <= T <=20
1 <= N <= 10^5
-10^6 <= x[ith], P <= 10^6
1 <= K <= 10^12
1 <= toys[ith] <= 10^9

Can anyone help me to solve it in python3.8 or java.
If someone would help me in solving this problem it would be great help for me. Thanks in advance.