Chip Cards

Johnny designs chips for chip cards. Each chip has $n$ ports on its upper boundary and $n$ ports on its bottom boundary. The upper ports are labelled from left to right as $1, 2, \ldots, n$. The bottom ports carry the same labels, also from left to right, but in a possibly different order. A pair of ports with the same label is joined by a straight-line path. The paths are grouped into layers, and paths in the same layer cannot cross.

The ports on each boundary are grouped into sockets. Each socket is a run of consecutive ports, and every port belongs to exactly one socket. The bottom sockets may have different lengths than the upper sockets. A socket can be switched, which reverses the order of the ports inside it.

Johnny has heard that he is going to be fired. He wants a small revenge, so he will design the next chip to be as expensive to produce as possible. The main production cost is the number of layers, so he switches each socket in the way that maximises the number of layers needed. This is harder than his usual work, and Johnny needs your help.

The first line contains a positive integer $n$ ($1 \le n \le 5000$), the number of ports on each boundary. The second line contains $n$ distinct integers from $\{1, 2, \ldots, n\}$, the labels of the bottom ports in order. The third line starts with an integer $k$ ($1 \le k \le n$), the number of upper sockets, followed by $k$ integers giving the number of ports in each consecutive upper socket. Each socket has at least one port, and the upper socket sizes sum to $n$. The fourth line describes the bottom sockets in the same format.

Print one positive integer, the maximum possible number of layers needed.

The first upper socket contains ports $1, 2, 3$, the second contains port $4$, and the third contains ports $5, 6, 7, 8$. By switching the sockets, the upper boundary can show these orders:

• $(1, 2, 3)$ $(4)$ $(5, 6, 7, 8)$
• $(1, 2, 3)$ $(4)$ $(8, 7, 6, 5)$
• $(3, 2, 1)$ $(4)$ $(5, 6, 7, 8)$
• $(3, 2, 1)$ $(4)$ $(8, 7, 6, 5)$