JOI Island est composée de $L$ secteurs, numérotés de $1$ à $L$ d'ouest en est. L'île possède $L-1$ routes, numérotées de $1$ à $L-1$. La route $i$ ($1 \le i \le L-1$) relie les secteurs $i$ et $i+1$ dans les deux sens.

Secteur $1$ — Route $1$ — Secteur $2$ — Route $2$ — Secteur $3$ — $\cdots$ — Secteur $L$

Les Olympiades internationales d'informatique (IOI 20XX) vont maintenant être organisées sur JOI Island ! Le problème est que l'île est célèbre pour sa chaleur extrême. Le risque de coup de chaleur est élevé, particulièrement pour les participants étrangers qui ne sont pas habitués à un environnement chaud. Les organisateurs des IOI ont donc décidé de prendre les mesures suivantes :

• Pour commencer, pour chaque $i$ ($1 \le i \le L$), ils préparent dans le secteur $i$ un hôpital pouvant accueillir $C_i$ personnes. Notez qu'il est possible que $C_i=0$.

• Pendant les IOI, lorsqu'une personne subit un coup de chaleur sur la route $x$ ($1 \le x \le L-1$), elle est envoyée à l'hôpital selon la procédure suivante :

  • Le patient est envoyé à l'hôpital du secteur $x$ ou du secteur $x+1$, selon celui qui n'est pas plein. Si aucun des deux hôpitaux n'est plein, les deux choix sont possibles. Si les deux hôpitaux sont pleins, le patient est envoyé par hélicoptère dans un hôpital général situé à l'extérieur de l'île.

Comme l'utilisation d'un hélicoptère coûte cher, les organisateurs souhaitent estimer le nombre maximal de patients qui seront transportés par hélicoptère. Ils considèrent à titre d'exemple le scénario suivant :

• Avant les IOI, aucun hôpital ne contient de patients.
• Pendant les IOI, $N$ personnes subiront un coup de chaleur sur JOI Island. Le patient numéro $j$ ($1 \le j \le N$) se trouve sur la route $X_j$.
• Pour chaque $j$ ($1 \le j \le N-1$), lorsque le patient numéro $j+1$ subit un coup de chaleur, le patient numéro $j$ et tous les précédents ont déjà été envoyés à l'hôpital. En raison de la gravité des symptômes des coups de chaleur, aucun patient ne quitte l'hôpital pendant les IOI.

Écrivez un programme qui, étant donnés le nombre de secteurs et les informations sur les hôpitaux et les patients victimes de coups de chaleur, calcule le nombre maximal de patients qui seront transportés par hélicoptère dans le scénario ci-dessus.

Entrée

Lisez les données suivantes sur l'entrée standard.

$$ \begin{array}{l} L\\ C_1\ C_2\ \cdots\ C_L\\ N\\ X_1\ X_2\ \cdots\ X_N \end{array} $$

Sortie

Écrivez une ligne sur la sortie standard. Elle doit contenir le nombre maximal de patients qui seront transportés par hélicoptère.

Contraintes

• $2 \le L \le 8\,000$.
• $0 \le C_i \le 8\,000$ ($1 \le i \le L$).
• $1 \le N \le 8\,000$.
• $1 \le X_j \le L-1$ ($1 \le j \le N$).
• Toutes les valeurs données sont des entiers.

Sous-tâches

1. (6 points) $X_1 \le X_2 \le \cdots \le X_N$.
2. (7 points) $L \le 18$, $N \le 18$, $C_i=1$ ($1 \le i \le L$).
3. (7 points) $L \le 18$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
4. (25 points) $L \le 100$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
5. (25 points) $L \le 100$, $N \le 100$.
6. (10 points) $L \le 600$, $N \le 600$.
7. (15 points) $L \le 3\,500$, $N \le 3\,500$.
8. (5 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

3
1 1 1
3
1 2 2

Sortie 1

1

Remarque

Si le déroulement suivant se produit, 1 patient sera transporté par hélicoptère.

1. Le premier patient est envoyé à l'hôpital du secteur $2$. Les nombres de patients dans les hôpitaux des secteurs $1,2,3$ deviennent alors respectivement $0,1,0$.
2. Le deuxième patient est envoyé à l'hôpital du secteur $3$. Les nombres de patients dans les hôpitaux des secteurs $1,2,3$ deviennent alors respectivement $0,1,1$.
3. Pour le troisième patient, comme les hôpitaux des secteurs $2$ et $3$ sont tous les deux pleins, le patient est transporté par hélicoptère dans un hôpital général à l'extérieur de l'île.

Puisqu'aucun déroulement ne permet de transporter 2 patients ou plus par hélicoptère, la sortie est 1.

Cette entrée d'exemple satisfait les contraintes des Sous-tâches 1, 2, 3, 4, 5, 6, 7, 8.

Entrée 2

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

Sortie 2

3

Remarque

Si le déroulement suivant se produit, 3 patients seront transportés par hélicoptère.

1. Le premier patient est envoyé à l'hôpital du secteur $2$. Les nombres de patients dans les hôpitaux des secteurs $1,2,3,4,5,6$ deviennent alors respectivement $0,1,0,0,0,0$.
2. Le deuxième patient est envoyé à l'hôpital du secteur $4$. Les nombres de patients dans les hôpitaux des secteurs $1,2,3,4,5,6$ deviennent alors respectivement $0,1,0,1,0,0$.
3. Le troisième patient est envoyé à l'hôpital du secteur $5$. Les nombres de patients dans les hôpitaux des secteurs $1,2,3,4,5,6$ deviennent alors respectivement $0,1,0,1,1,0$.
4. Pour le quatrième patient, comme les hôpitaux des secteurs $4$ et $5$ sont tous les deux pleins, le patient est transporté par hélicoptère dans un hôpital général à l'extérieur de l'île.
5. Le cinquième patient est envoyé à l'hôpital du secteur $3$. Les nombres de patients dans les hôpitaux des secteurs $1,2,3,4,5,6$ deviennent alors respectivement $0,1,1,1,1,0$.
6. Pour le sixième patient, comme les hôpitaux des secteurs $2$ et $3$ sont tous les deux pleins, le patient est transporté par hélicoptère dans un hôpital général à l'extérieur de l'île.
7. Pour le septième patient, comme les hôpitaux des secteurs $3$ et $4$ sont tous les deux pleins, le patient est transporté par hélicoptère dans un hôpital général à l'extérieur de l'île.

Puisqu'aucun déroulement ne permet de transporter 4 patients ou plus par hélicoptère, la sortie est 3.

Cette entrée d'exemple satisfait les contraintes des Sous-tâches 2, 3, 4, 5, 6, 7, 8.

Entrée 3

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

Sortie 3

1

Remarque

Cette entrée d'exemple satisfait les contraintes des Sous-tâches 1, 5, 6, 7, 8.

Entrée 4

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

Sortie 4

2

Remarque

Cette entrée d'exemple satisfait les contraintes des Sous-tâches 5, 6, 7, 8.

Entrée 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

Sortie 5

3

Remarque

Cette entrée d'exemple satisfait les contraintes des Sous-tâches 5, 6, 7, 8.