Batrick has gifted Envy a field of $$$n$$$ pumpkins for Halloween! The pumpkins are arranged in a row numbered $$$1 \dots n$$$ from left to right. Pumpkin $$$i$$$ has tastiness $$$a_i$$$ and quality $$$b_i$$$, and Envy wishes to maximize the sum of the tastiness of the pumpkins he eats. Envy will perform $$$n$$$ operations, and on the $$$i$$$-th operation, he can do one of the following:
$$$1$$$: Carve a jack-o-lantern into the $$$i$$$-th pumpkin, illuminating all pumpkins at most $$$b_i$$$ spaces away.
$$$2$$$: Eat the $$$i$$$-th pumpkin only if it is lit up by a jack-o'-lantern, gaining tastiness $$$a_i$$$. This destroys the pumpkin.
$$$3$$$: Swap the $$$i$$$-th pumpkin with the $$$i - 1$$$-th pumpkin, if it exists. Note that the pumpkins retain their original properties after the swap, so their $$$a$$$ and $$$b$$$ values will be swapped, as well as the status of whether they have been carved or not. As such, the pumpkins that are illuminated may change as a result of a swap.
What is the maximum sum of $$$a_i$$$ over all pumpkins Envy consumes?
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 1000$$$). The description of the test cases follows.
The first line of each testcase contains an integer, $$$n$$$ ($$$1 \leq n \leq 5000$$$).
The second line contains $$$n$$$ integers, $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
The line after contains $$$n$$$ more integers, $$$b_1, b_2, \dots, b_n$$$ ($$$0 \leq b_i \lt n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$5000$$$.
For each test case, output the maximum tastiness sum Envy can achieve.
233 1 22 2 251 1 5 5 53 2 0 1 0
3 15
In the first test case Envy can carve pumpkin $$$1$$$ and eat pumpkins $$$2$$$ and $$$3$$$.
In the second test case Envy should carve pumpkin $$$1$$$, swap pumpkins $$$1$$$ and $$$2$$$, then eat the remaining pumpkins.
Problem Credits: Patrick Deng
