Background

JOI's lunch consists of Xiao Long Bao bought from a Chinese restaurant. Xiao Long Bao is a dish made with dough wrapping around filling and hot soup. When eaten, the soup splashes out.

Problem Description

JOI has ordered a set of Xiao Long Bao, consisting of \( N \) Xiao Long Baos with different fillings. These \( N \) Xiao Long Baos are arranged in a row at equal intervals, numbered from 1 to \( N \). The distance between the \( i \)-th and \( j \)-th Xiao Long Bao is the absolute value \( \vert i - j \vert \).

JOI eats the Xiao Long Baos in order. Initially, the deliciousness of all Xiao Long Baos is 0. When eating the \( i \)-th Xiao Long Bao, the soup splashes around, and all Xiao Long Baos within a distance \( D_i \) from the \( i \)-th Xiao Long Bao are splashed with soup, increasing their deliciousness by \( A_i \). That is, when eating the \( i \)-th Xiao Long Bao, 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 yet been eaten increases by \( A_i \).

JOI wants to maximize the total deliciousness of the Xiao Long Baos by carefully choosing the order in which he eats them.

Input Format

The input consists of 3 lines.

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

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

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

Output Format

Output a single line containing the maximum total deliciousness of the Xiao Long Baos that JOI can achieve.

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

For Sample 1: Eating in the order of the 5th, 3rd, 1st, 2nd, and 4th Xiao Long Baos results in a total deliciousness of 20, as no other order can achieve a higher deliciousness.

This problem is from the 2014 Japanese Olympiad in Informatics (JOI) Preliminary Round, Problem 6.

见题面 Input 部分

见题面 Output 部分