A car is moving on a straight line of length N meters.

The car has a fixed fuel tank capacity of K liters and it spends 1 liter per meter. There are M fuel filling stations along the straight line where the ith station is located at position a[i] and sells 1 liter of fuel for b[i] dollars.

It is given that the car can only refill the tank fully when it stops at some station for refueling. This means that if the tank contains 3 liters and its capacity was 10 liters, the car can buy exactly7 liters of fuel (otherwise the car will not stop at the fuel station for refueling).

Given that the car starts at position 0 moving in one direction to the end of the line and it can buy fuel from any fuel station it stops at. Your task is to choose which stations to buy from in order to reach the end of the line with the minimum possible cost. If it’s impossible to reach the end of the line return -1.

Note: It is guaranteed that there is always a fuel station at position 0.

Input Format The first line contains an integer, N, denoting the length of the road.
The next line contains an integer, K, denoting the tank's capacity.
The next line contains an integer, M, denoting the number of elements in a (the number of stations).
Each line i of the M subsequent lines (where 0 ≤ i < M) contains an integer describing ai (stations' locations).
Each line i of the M subsequent lines (where 0 ≤ i < M) contains an integer describing bi (the cost of one liter in each station).

Constraints
1 <= N <= 10^5
1 <= K <= 10^5
1 <= M <= 10^3
1 <= a[i] <= N
1 <= b[i] <= 10^9

Sample Input Sample Output Explanation
10
5
4
0
4
5
8
1
2
3
4 16

10
5
3
0
1
4
1
3
2 -1

This is what I tried but giving wrong answer

static long[] dp;
	
	public static long car_recur(int N,int K,int M,int[] a,int[] b){
		dp = new long[M];
		Arrays.fill(dp, -1);
		
		long ans = Long.MAX_VALUE;
		for (int i = M - 1; i >= 0; i--) {
			if (a[i] != N && N - a[i] <= K) {
				long tmp = recur(i, K, a, b);
				if (tmp != -1) {
					ans = Math.min(ans, tmp);
				}
			}
		}
		return ans == Long.MAX_VALUE ? - 1 : ans;
	}
	
	private static long recur(int fuelStop, int K, int[] a, int[] b) {
		if (dp[fuelStop] != -1) return dp[fuelStop];
		if (fuelStop == 0) return (long)b[0] * K;
		long ans = Long.MAX_VALUE;
		for (int i = fuelStop - 1; i >= 0; i--) {
			if (a[fuelStop] - a[i] <= K) {
				long tmp = recur(i, K, a, b);
				if (tmp != -1) {
					ans = Math.min(ans, tmp + b[fuelStop] * (a[fuelStop] - a[i]));
				}
			}
		}
		return dp[fuelStop] = ans == Long.MAX_VALUE ? -1 : ans;
	}