P8877 [ChuanZhi Cup #5 Preliminary] I - The Unending Banquet

The school is organizing a banquet. Lianzi and Meili found that the school’s structure is very complex. Among students, there are relationships of departments and supervisors. Inside each department, the supervisor relationship forms a single chain. The student with the highest rank in one department may also be restricted by some student in another department. Lianzi and Meili also attend the banquet. But they have their own ways to judge the attending students. For example, they like some departments more and are not interested in others. They also have different opinions about students at different ranks. As described in a classic problem, every student does not want to attend the banquet together with their direct supervisor. Meili wants to know, in the best case, how many students attending the banquet are liked by her.

The student society can be seen as a node array arranged into an isosceles right triangle. This node array has $n$ rows, and row $i$ has $i$ nodes. We label the node in row $i$ and column $j$ as $(i,j)$. - These nodes have weights. Specifically, the weight of node $(i,j)$ is $r_i\oplus c_j$, where $r$ and $c$ are given $01$ sequences, and $\oplus$ is the **bitwise XOR** operation. - These nodes are connected by edges. Specifically, for $1\le i< n$, $1\le j\le i$, there is an edge connecting $(i,j)$ and $(i+1,j)$. In addition, for $2\le i\le n$, there is also an edge connecting $(i,i)$ and $(i-1,a_i)$. Here, $a$ is a given sequence. Now you need to choose some nodes such that **no two chosen nodes are connected by an edge**, and maximize the **sum of weights** of the chosen nodes. The figure below shows an example with $n=8$. Black nodes have weight $1$, and white nodes have weight $0$. **Note**: The picture only symbolically shows part of the values of $r_i$ and $c_i$. The actual values in the picture are $\def\t{,\allowbreak}r=\{1\t 1\t 0\t 1\t 0\t 0\t 0\t 1\}\t c=\{0\t 0\t 1\t 0\t 1\t 1\t 0\t 0\}$. 

- The first line contains a positive integer $n$, describing the size of the node array. - The second line contains $n$ integers $0$ or $1$, describing the values of $r_i$. - The third line contains $n$ integers $0$ or $1$, describing the values of $c_i$. - The fourth line contains $n-1$ positive integers, where the $i$-th number describes the value of $a_{i+1}$.

- Output one integer in a single line, describing the maximum possible sum of weights of the selected nodes.

### Sample Explanation One possible selection is shown in the figure below. The orange-red blocks indicate the selected nodes.  ### Constraints and Notes For all testdata, it is guaranteed that $1\le n\le 10^6$, $r_i\in\{0,1\}$, $c_i\in\{0,1\}$, $1\le a_i