La isla JOI consta de $L$ distritos, numerados del $1$ al $L$ de oeste a este. Hay $L-1$ carreteras en la isla, numeradas del $1$ al $L-1$. La carretera $i$ ($1\le i\le L-1$) conecta los distritos $i$ e $i+1$ en ambos sentidos.

¡Se planea celebrar la Olimpiada Internacional de Informática (IOI 20XX) en la isla JOI! El problema es que la isla es famosa por su calor extremo. Existe un alto riesgo de sufrir un golpe de calor, especialmente para los concursantes extranjeros que no están acostumbrados a un ambiente caluroso. Por ello, los organizadores de la IOI decidieron tomar las siguientes medidas:

• Primero, para cada $i$ ($1\le i\le L$), preparan un hospital en el distrito $i$ con capacidad para $C_i$ personas. Ten en cuenta que puede ocurrir que $C_i=0$.

• Durante la IOI, cuando una persona sufre un golpe de calor en la carretera $x$ ($1\le x\le L-1$), la envían a un hospital mediante el siguiente procedimiento:

  • Envían al paciente al hospital del distrito $x$ o al del distrito $x+1$, eligiendo uno que no esté lleno. Si ninguno de los dos está lleno, se puede elegir cualquiera. Si ambos están llenos, envían al paciente en helicóptero a un hospital general fuera de la isla.

Como el uso del helicóptero es costoso, los organizadores quieren estimar el número máximo de pacientes que se enviarán en helicóptero. Consideran el siguiente escenario a modo de ejemplo:

• Antes de la IOI no hay pacientes en ningún hospital.
• Durante la IOI, $N$ personas sufrirán un golpe de calor en la isla JOI. El $j$-ésimo paciente ($1\le j\le N$) aparece en la carretera $X_j$.
• Para cada $j$ ($1\le j\le N-1$), cuando el paciente $j+1$ sufre un golpe de calor, el paciente $j$ y todos los anteriores ya han sido enviados a un hospital. Debido a la gravedad de los síntomas del golpe de calor, ningún paciente abandona el hospital durante la IOI.

Escribe un programa que, dados el número de distritos y la información sobre los hospitales y los pacientes con golpe de calor, calcule el número máximo de pacientes que se enviarán en helicóptero en el escenario anterior.

Entrada

Lee los siguientes datos de la entrada estándar.

$$ \begin{aligned} &L\\ &C_1\ C_2\ \cdots\ C_L\\ &N\\ &X_1\ X_2\ \cdots\ X_N \end{aligned} $$

Salida

Escribe una línea en la salida estándar. Debe contener el número máximo de pacientes que se enviarán en helicóptero.

Restricciones

• $2\le L\le8\,000$.
• $0\le C_i\le8\,000$ ($1\le i\le L$).
• $1\le N\le8\,000$.
• $1\le X_j\le L-1$ ($1\le j\le N$).
• Todos los valores dados son enteros.

Subtareas

1. (6 puntos) $X_1\le X_2\le\cdots\le X_N$.
2. (7 puntos) $L\le18$, $N\le18$, $C_i=1$ ($1\le i\le L$).
3. (7 puntos) $L\le18$, $N\le100$, $C_i=1$ ($1\le i\le L$).
4. (25 puntos) $L\le100$, $N\le100$, $C_i=1$ ($1\le i\le L$).
5. (25 puntos) $L\le100$, $N\le100$.
6. (10 puntos) $L\le600$, $N\le600$.
7. (15 puntos) $L\le3\,500$, $N\le3\,500$.
8. (5 puntos) No hay restricciones adicionales.

Ejemplos

Entrada 1

3
1 1 1
3
1 2 2

Salida 1

1

Nota

Si ocurre lo siguiente, se enviará a 1 paciente en helicóptero.

1. Se envía al primer paciente al hospital del distrito $2$. Entonces, el número de pacientes en los hospitales de los distritos $1,2,3$ será $0,1,0$, respectivamente.
2. Se envía al segundo paciente al hospital del distrito $3$. Entonces, el número de pacientes en los hospitales de los distritos $1,2,3$ será $0,1,1$, respectivamente.
3. Para el tercer paciente, como los hospitales de los distritos $2$ y $3$ están llenos, se envía al paciente en helicóptero a un hospital general fuera de la isla.

Como no hay ningún caso en el que se envíen a 2 o más pacientes en helicóptero, se imprime $1$.

Esta entrada de ejemplo satisface las restricciones de las subtareas 1, 2, 3, 4, 5, 6, 7, 8.

Entrada 2

6
1 1 1 1 1 1
7
1 3 5 4 2 2 3

Salida 2

3

Nota

Si ocurre lo siguiente, se enviarán a 3 pacientes en helicóptero.

1. Se envía al primer paciente al hospital del distrito $2$. Entonces, el número de pacientes en los hospitales de los distritos $1,2,3,4,5,6$ será $0,1,0,0,0,0$, respectivamente.
2. Se envía al segundo paciente al hospital del distrito $4$. Entonces, el número de pacientes en los hospitales de los distritos $1,2,3,4,5,6$ será $0,1,0,1,0,0$, respectivamente.
3. Se envía al tercer paciente al hospital del distrito $5$. Entonces, el número de pacientes en los hospitales de los distritos $1,2,3,4,5,6$ será $0,1,0,1,1,0$, respectivamente.
4. Para el cuarto paciente, como los hospitales de los distritos $4$ y $5$ están llenos, se envía al paciente en helicóptero a un hospital general fuera de la isla.
5. Se envía al quinto paciente al hospital del distrito $3$. Entonces, el número de pacientes en los hospitales de los distritos $1,2,3,4,5,6$ será $0,1,1,1,1,0$, respectivamente.
6. Para el sexto paciente, como los hospitales de los distritos $2$ y $3$ están llenos, se envía al paciente en helicóptero a un hospital general fuera de la isla.
7. Para el séptimo paciente, como los hospitales de los distritos $3$ y $4$ están llenos, se envía al paciente en helicóptero a un hospital general fuera de la isla.

Como no hay ningún caso en el que se envíen a 4 o más pacientes en helicóptero, se imprime $3$.

Esta entrada de ejemplo satisface las restricciones de las subtareas 2, 3, 4, 5, 6, 7, 8.

Entrada 3

6
4000 1 1 0 4000 1
5
1 1 2 3 5

Salida 3

1

Nota

Esta entrada de ejemplo satisface las restricciones de las subtareas 1, 5, 6, 7, 8.

Entrada 4

5
1 2 2 2 1
8
2 3 2 1 4 1 2 3

Salida 4

2

Nota

Esta entrada de ejemplo satisface las restricciones de las subtareas 5, 6, 7, 8.

Entrada 5

10
2 2 2 2 2 2 2 2 2 2
18
1 3 5 7 9 2 4 6 8 1 3 5 7 9 2 4 6 8

Salida 5

3

Nota

Esta entrada de ejemplo satisface las restricciones de las subtareas 5, 6, 7, 8.