Question
Maximal Sum with Lookback Restriction
Shreyas is playing a game with an array of integers.
At position i, the array contains an integer a[i].
If Shreyas picks the element at index i:
-
he adds
a[i]to his score, and -
he cannot pick any of the previous
a[i]indices (that is, indicesi-1, i-2, …, i-a[i]become forbidden).
Your task is to help Shreyas determine the maximum total sum he can achieve.
Input
The first line contains an integer n — the number of elements in the array.
The second line contains n space-separated integers a[1], a[2], …, a[n].
The second line contains n space-separated integers a[1], a[2], …, a[n].
Output
Print a single integer — the maximum sum obtainable under the given restriction.
Example
Input
5
3 2 1 4 5
Output
5
Explanation:
If we pick indices 1 and 3 → score = 3 + 1 = 4.
The best choice is to pick index 5 → score = 5.
Hence, the answer is 5.
5
3 2 1 4 5
Output
5
Explanation:
If we pick indices 1 and 3 → score = 3 + 1 = 4.
The best choice is to pick index 5 → score = 5.
Hence, the answer is 5.