Card Game Strategy Optimization

You and Xiao Yang are playing a card game.

Both of you have 3 cards: 0, 1 and 2. The game consists of \(N\) rounds. In each round \(i\) (\(1 \le i \le N\)), both players play one card. The outcome of a round is decided by the rules below:

• If both cards are the same, it is a tie and each player gets \(a_i\) points.
• If the cards are different, the winning rule is defined as follows: card \(1\) beats card \(0\), card \(2\) beats card \(1\) and card \(0\) beats card \(2\). In a win, the winner gets \(2a_i\) points and the loser gets \(0\) points.

Originally the game is played normally; however, soon Xiao Yang and you decided to spice up the rules. Before the game begins, Xiao Yang declares his sequence of moves for all \(N\) rounds. You, on the other hand, are subject to a restriction: in round \(1\) you can freely choose any card; but from round \(2\) onward, you must either use the same card as in the previous round or choose to "swap" to a different card. Each time you swap (i.e. change the card from the previous round), you incur an additional penalty. Specifically, if you swap a total of \(t\) times during the \(N\) rounds, you will have a penalty of \(b_1+b_2+\cdots+b_t\) points deducted from your total score (the penalty for the \(j\)th swap is \(b_j\)).

Your task is to determine the maximum score you can obtain by the end of the game.

The scoring in each round is computed according to the following function:

\[ f(x,y) = \begin{cases} a_i & \text{if } x = y, \\ 2a_i & \text{if } x = (y+1) \bmod 3, \\ 0 & \text{otherwise.} \end{cases} \]

Here, \(x\) denotes the card you play in the round and \(y\) denotes the card Xiao Yang plays. Note that the winning condition for a win is \(x = (y+1) \bmod 3\).

inputFormat

The input consists of four lines:

1. An integer \(N\) representing the number of rounds.
2. \(N\) space-separated integers \(a_1, a_2, \ldots, a_N\) representing the base points in each round.
3. \(N-1\) space-separated integers \(b_1, b_2, \ldots, b_{N-1}\) where \(b_j\) is the penalty for the \(j\)th card swap.
4. \(N\) space-separated integers representing Xiao Yang's planned moves for rounds 1 through \(N\). Each integer is either 0, 1, or 2.

It is guaranteed that \(N \ge 2\) and all input values are valid. The moves provided for Xiao Yang are integers from the set \({0,1,2}\).

outputFormat

Output a single integer, the maximum score you can obtain after \(N\) rounds considering both the points earned in each round and the penalties for switching cards.

sample

3
1 2 3
1 100
0 1 2

9