Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1139.

Problem Description

You and Xiao Yang are playing a card game.

Each of you has $3$ cards: $0$, $1$, and $2$. You will play $N$ rounds. In each round, both players play one card, and the winner is decided by the rules: $1$ beats $0$, $2$ beats $1$, and $0$ beats $2$. In round $i$, the winner gains $2 \times a_i$ points and the loser gains $0$ points. If both players play the same card, it is a draw and both gain $a_i$ points $(i=1,2,\cdots,N)$.

After playing for a while, you feel this is too boring, so both of you make different new rules for yourselves. Before the whole game starts, Xiao Yang will decide all of his plays for all $N$ rounds and tell you his entire plan. Starting from round $2$, you must either keep playing the same card as in the previous round, or record one “card change”. At the end of the game, if you changed cards $t$ times, you will be additionally deducted $b_1+\cdots+b_t$ points.

Please compute the maximum score you can obtain.

Input Format

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

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

The third line contains $N-1$ non-negative integers $b_1,\cdots,b_{N-1}$ separated by single spaces, representing the penalty for changing cards, as described in the statement. Since the game lasts for $N$ rounds, you can change cards at most $N-1$ times.

The fourth line contains $N$ integers $c_1,\cdots,c_N$ separated by single spaces, representing the cards Xiao Yang plays from round $1$ to round $N$ in order. It is guaranteed that $c_i\in\{0,1,2\}$.

Output Format

Output one integer in one line, the maximum score you can obtain.

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

219

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

56

Hint

Sample Explanation 1

You can play $0$ in round $1$, and keep it unchanged in rounds $2,3$. In this way, you lose rounds $1,2$, but win round $3$ and gain $2\times10=20$ points;

Then, you can change to $1$ in round $4$ at the cost of deducting $1$ point, and win round $4$, gaining $2\times100=200$ points.

In this way, the highest total score you can get is $20+200-1=219$.

Constraints

For $30\%$ of the testdata, $N\le15$.

For $60\%$ of the testdata, $N\le100$.

For all testdata, $N \le 1,000$; and $0 \le a_i,b_i \le 10^6$.

Translated by ChatGPT 5