There are \(N\) points placed on a number line at position \(1, 2,..., N.\)
Initially, you are at point \(1\) and want to find the minimum cost to reach each of the \(N\) points. You are allowed to move only towards +ve x-axis.
Let's say, after certain moves, you are at point \(i (
- type \(1:\) by moving to the next point i.e point \(i+1\) which cost \(A_i.\)
- type \(2:\) by moving to point \(j\) if and only if \(i∈[ L_j, R_j ]\) which cost \(B_i.\) \(\)
Find the minimum cost to reach each of the \(N\) points.
Input Format
- The first line contains \(T\) denoting the number of test cases. The description of \(T \) test cases is as follows:
- Each test case consists of multiple lines of input.
- The first line of each test case contains one integer \(N\) — the number of points.
- The second line consists of \(N-1\) space-separated integers denoting the elements of array \(A\).
- The Third line consists of \(N\) space-separated integers denoting the elements of array \(B\).
- The Fourth line consists of \(N\) space-separated integers denoting the elements of array \(L\).
- The Fifth line consists of \(N\) space-separated integers denoting the elements of array \(R\).
Output Format
- For each test case, output on a new line, the minimum cost to reach each of the \(N\) points.
Constraints
- \(1 \leq T \leq 10^{5}\)
- \(2 \leq N \leq 2\cdot10^{5}\)
- \(1 \leq A_i, B_i \leq 10^{9}\)
- \(1 \leq L_i \leq R_i \leq i\)
- \(\text { It is guaranteed that sum of N over all test cases doesn't exceed }\ 2\cdot 10^{5}\)
2 5 5 3 1 1 4 2 4 1 1 1 1 2 1 3 1 2 2 4 5 6 6 8 5 10 5 7 4 5 3 8 1 1 1 2 2 1 4 1 2 3 4 3 5
0 4 6 4 5 0 6 10 10 7 12
Test case 1:
-
You are initially at point \(1\) ( \(cost = 0\) ).
-
The only way to reach point \(2\) is by using move \(1 → 2\).
-
Since, point \(2\) is next to point \(1\) so we can perform the move \(1 → 2\) using move of type \(1\) with the cost of \(A_1 = 5.\)
-
Also, \(1∈[ L_2=1, R_2=2 ]\) so we can perform the move \(1 → 2\) using move of type \(2\) with the cost of \(B_1 = 4.\)
-
Hence, the minimum cost is \(min( 5, 4 ) = 4.\)
-
-
The only way to reach point \(3\) is by using moves \(1 → 2→ 3\) because we can't move directly \(1 → 3\) since, \(1 ∉ [L_3=2, R_3=2]\).
-
We have already found the optimal way to reach point \(2\) with the minimum cost of \(4\) above.
-
Now, to reach from \(2→ 3\), we again have both types of move possible because point \(3\) is next to point \(2\) and also \(2∈[ L_3=2, R_3=2 ].\)
-
For move \(2→ 3\), move of type \(1\) costs \(A_2 = 3\) and move of type \(2\) costs \(B_2 = 2.\)
-
Hence, the minimum cost is \(4+min( 3, 2 ) = 4+2=6.\)
-
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor