Problem Description

You and Xiaoyang are playing a card game.

Each of you has 3 cards, numbered 0, 1, and 2. You will play N rounds of the game, where in each round both players must play one card. The rules for determining the winner are: 1 beats 0, 2 beats 1, and 0 beats 2. The winner of the i-th round gets 2 × a_i points, while the loser gets no points. If both players play the same card, it is considered a draw, and both players get a_i points (i=1,2,...,N).

After playing for a while, you both find it too monotonous, so you each create new rules for yourselves. Xiaoyang will determine his entire sequence of plays before the game starts and will inform you of his entire plan. Starting from the second round, you can either continue playing the same card as the previous round or make a "card change". At the end of the game, if you have made t card changes, you will be penalized an additional b_1 + ... + b_t points.

Calculate the maximum number of points you can earn.

Input Format

The first line contains an integer N, representing the number of rounds.

The second line contains N non-negative integers a_1, ..., a_N separated by single spaces, as described in the problem.

The third line contains N-1 non-negative integers b_1, ..., b_{N-1} separated by single spaces, representing the penalty for changing cards, as described in the problem. Since the game has N rounds, you can make at most N-1 card changes.

The fourth line contains N integers c_1, ..., c_N separated by single spaces, representing the cards Xiaoyang will play from the 1st to the N-th round. It is guaranteed that c_i ∈ {0, 1, 2}.

Output Format

A single line containing an integer, representing the maximum number of points you can earn.

Sample Input and Output

Input Sample #1

4
1 2 10 100
1 100 1
1 1 2 0

Output Sample #1

219

Input Sample #2

6
3 7 2 8 9 4
1 3 9 27 81
0 1 2 1 2 0

Output Sample #2

56

Notes

Sample Explanation 1

You can play 0 in the 1st round and maintain the same card in the 2nd and 3rd rounds, losing the 1st and 2nd rounds but winning the 3rd round, earning 2 × 10 = 20 points.

Then, you can change to playing 1 in the 4th round at the cost of 1 point and win the 4th round, earning 2 × 100 = 200 points.

Thus, you can achieve the highest total score of 20 + 200 - 1 = 219.

Data Range

For 30% of the test cases, N ≤ 15.

For 60% of the test cases, N ≤ 100.

For all test cases, N ≤ 1,000; 0 ≤ a_i, b_i ≤ 10^6.

见题面 Input 部分

见题面 Output 部分