Anyone got approach for this dp problem ?

Problem Description

In this problem we consider two stairways, A and B, which are parallel to each other. Both stairways, A and B, have N steps each where A[i], B[i] represent i-th step of A and B respectively.

Each step has some amount of penalty associated and if you use that step you will be penalised by the same amount. After taking few steps you will accumulate penalty of all of the steps you visited.
You have a maximum jump length of K i.e., from A[i] you can jump forward to A[i+1] or A[i+2] … or A[i+K] without using any steps in between.

You can also jump across the stairways with an extra penalty P for changing stairways. For example from A[i] you can jump to B[i+1] or B[i+2] … or B[i+K] with an additional penalty P along with the penalty of the step you visit. You can also jump from stairway B to stairway A and that too incurs an additional penalty P along with the penalty of the step you visit.

Observe that from each step you can jump forward only. Your final penalty will be penalty of all the steps you visited plus P times the number of times you crossed the stairways.
You can start from A[1] or B[1] and should reach A[N] or B[N] minimising the penalty accumulated on the way. Find the minimum penalty you will accumulate.

Input

The fist line in input is equal to T, the number of test cases. Then follows the description of T test cases. The first line in each test case has three integers N, the number of steps in both stairways, K, maximum jump length, P, penalty for crossing the stairs. On the second line of each test case there are N integers where ith integer represents penalty of step A[i]. On the third line of each test there are N integers where ith integer represents penalty of step B[i].
Output

For each test case, output a single line containing the minimum penalty you can accumulate on your path starting from { A[1] or B[1] } and ending on { A[N] or B[N] }.
Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 1000

0 ≤ P ≤ 1000

1 ≤ K ≤ N

0 ≤ A[i], B[i] ≤ 1000

Example

Input:

6

4 1 0

1 2 3 4

1 2 3 4

4 1 0

1 2 3 4

4 3 2 1

4 2 0

1 2 3 4

4 3 2 1

4 1 10

1 2 3 4

4 3 2 1

4 2 10

1 2 3 4

4 3 2 1

5 1 50

0 0 102 104 0

101 103 0 0 105

Output:

10

6

4

10

7

100

Example test case 1.
Both the stairs are same and jump length is 1 , so you need to visit all steps on single stairway

Min Path : A[1], A[2], A[3], A[4]

Hence answer is 10 for first test case.
Example test case 2.
A has lesser values initially and then B has lesser values later. So starting from A and jumping to B would be optimal

Min Path : A[1] , A[2], B[3], B[4]

Hence answer is 6 for second test case.
Example test case 3.
Min Path : A[1], B[3], B[4]

Hence answer is 4 for third test case.
Example test case 4.
Min Path : A[1], A[2], A[3], A[4]

We will not cross because penalty for crossing is very high.
Hence answer is 10 for fourth test case.
Example test case 5.
Min Path : A[1], A[2], A[4]

Hence answer is 7 for fifth test case.
Example test case 6.
Min Path : A[1], A[2], B[3], B[4], A[6]

Let minP[k][i] be the minimum penalty if you’re at step i in stairway k (k=0 for stairway A, k=1 for stairway B).

minP[0][0] == A[1][0] == 0

minP[k][i] == (penalty of this step) + min( min(minP[k][j >= i-K]), P+min(minP[1-k][j >= i-K]) )

That’s it. Easy.

1 Like