Jump Over This <Upgrad>
Practice
0 (0 votes)
Introduction to dynamic programming 2
Dynamic programming
Recursion
Medium
Algorithms
Dynamic programming
Problem
81 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

You are given two arrays of size \(N\). Array 1 is \(val\) denoting values, and Array 2 is \(h\) denoting heights. At every position of the array, we can either pick the value \(val_i\) or increase the current height by \(h_i\). You are allowed to perform exactly 1 move at each position of array.

You are provided with \(M\) indexes \(I_i\). For each of these indexes, you are given with \({min\_height}_i\), which denotes the minimum height required to reach that index. Our height must be minimum of \({min\_height}_i\) before reaching the position \(i\) . If our height is less than \({min\_height}_i\) at index \(I_i\), we can not jump to index \(I_i\).

Note: All the indices  \(I_i\) are distinct.

Your aim is to maximise the sum of \(val_i\) picked, at the end of the array, subject to given constraints. You need to print -1, incase there is no way of reaching the end of the array.

Input

The first line of input contains a number \(T\) that denotes the total number of test cases.
The first line for each test case consists of a number \(N\).
The next line contains \(N\) space separated integers corresponding to \(val_i\).
The next line contains \(N\) space separated integers corresponding to \(h_i\).
The next line contains a single number \(M\).
The next line contains \(M\) space separated integers corresponding to \(I_i\).
The next line contains \(M\) space separated integers corresponding to \({min\_height}_i,\).

Output

Output a single integer corresponding to maximum possible sum of \(val_i\) picked, at the end of the array, subject to given constraints.

Constraints
\(1 \le T \le 10\\ 1 \le N \le 1000\\ 0 \le M \le N\\ 0 \le val_i \le 10^9\\ 0\le h_i\le 10^9\\ 0 \le I_i \le N-1\\ 0 \le {min\_height}_i \le 10^3\\ \)

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

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
11 votes
Tags:
BitmaskDynamic ProgrammingAlgorithmsApprovedMedium
Points:30
1 votes
Points:30
8 votes
Tags:
Introduction to Dynamic Programming-2AlgorithmsMediumDPDynamic Programming