Problem Description

JOI is having lunch at a Chinese restaurant and decides to order xiao long bao, a dish known for its hot soup that splashes around when eaten. The set of xiao long bao JOI orders consists of \( N \) different xiao long bao arranged in a row, numbered from 1 to \( N \). The distance between the \( i \)-th and \( j \)-th xiao long bao is the absolute value \( |i - j| \).

JOI will eat the xiao long bao in some order. Initially, the deliciousness of all xiao long bao is 0. When the \( i \)-th xiao long bao is eaten, its juice splashes around, affecting the xiao long bao that have not been eaten yet, within a distance \( D_i \) from the \( i \)-th xiao long bao. The deliciousness of these affected xiao long bao increases by \( A_i \). That is, when the \( i \)-th xiao long bao is eaten, the deliciousness of the \( j \)-th xiao long bao (where \( 1 \leq j \leq N \) and \( i - D_i \leq j \leq i + D_i \)) that has not been eaten yet increases by \( A_i \).

JOI wants to maximize the total deliciousness of the xiao long bao he eats by choosing the best order. Write a program to determine the maximum total deliciousness JOI can achieve.

Input Format

The input consists of 3 lines.

The first line contains a single integer \( N \) (\( 1 \leq N \leq 100 \)).

The second line contains \( N \) integers \( D_1, D_2, \ldots, D_N \) (\( 0 \leq D_i \leq 7 \)), separated by spaces.

The third line contains \( N \) integers \( A_1, A_2, \ldots, A_N \) (\( 0 \leq A_i \leq 1000 \)), separated by spaces.

Output Format

Output a single line containing the maximum total deliciousness of the xiao long bao JOI can eat.

Sample Input and Output

Sample Input #1

5
1 0 1 1 2
0 2 6 3 4

Sample Output #1

20

Sample Input #2

10
5 2 7 2 6 5 3 5 3 6
8 7 8 4 0 6 0 10 10 0

Sample Output #2

237

Notes/Hints

Sample Explanation 1

In the first sample input, eating the xiao long bao in the order of 5th → 3rd → 1st → 2nd → 4th results in a total deliciousness of 20. There is no way to exceed a total of 20, so this is the best possible outcome.

见题面 Input 部分

见题面 Output 部分