JOI Island besteht aus $L$ Bezirken, die von Westen nach Osten von $1$ bis $L$ nummeriert sind. Auf der Insel gibt es $L-1$ Straßen, nummeriert von $1$ bis $L-1$. Straße $i$ ($1\le i\le L-1$) verbindet die Bezirke $i$ und $i+1$ in beiden Richtungen.

Nun soll die Internationale Informatikolympiade (IOI 20XX) auf JOI Island stattfinden! Besorgniserregend ist, dass die Insel für ihre extreme Hitze bekannt ist. Es besteht ein hohes Risiko für einen Hitzschlag, insbesondere für ausländische Teilnehmer, die nicht an eine heiße Umgebung gewöhnt sind. Daher haben die Organisatoren der IOI folgende Maßnahmen beschlossen:

• Zunächst richten sie für jedes $i$ ($1\le i\le L$) im Bezirk $i$ ein Krankenhaus mit einer Kapazität von $C_i$ Personen ein. Beachte, dass auch $C_i=0$ vorkommen kann.

• Wenn während der IOI eine Person auf Straße $x$ ($1\le x\le L-1$) einen Hitzschlag erleidet, wird sie nach folgendem Verfahren ins Krankenhaus gebracht:

  • Der Patient wird in das Krankenhaus von Bezirk $x$ oder $x+1$ gebracht, je nachdem, welches noch nicht voll ist. Sind beide Krankenhäuser noch nicht voll, ist jede der beiden Möglichkeiten zulässig. Sind beide Krankenhäuser voll, wird der Patient per Hubschrauber in ein allgemeines Krankenhaus außerhalb der Insel gebracht.

Da der Einsatz von Hubschraubern teuer ist, möchten die Organisatoren die maximale Anzahl von Patienten abschätzen, die per Hubschrauber transportiert werden. Sie betrachten beispielhaft folgendes Szenario:

• Vor der IOI gibt es in keinem Krankenhaus Patienten.
• Während der IOI erleiden $N$ Personen auf JOI Island einen Hitzschlag. Der $j$-te ($1\le j\le N$) Patient tritt auf Straße $X_j$ auf.
• Für jedes $j$ ($1\le j\le N-1$) gilt: Wenn der $(j+1)$-te Patient einen Hitzschlag erleidet, sind der $j$-te Patient und alle früheren Patienten bereits ins Krankenhaus gebracht worden. Aufgrund der schweren Symptome eines Hitzschlags verlässt während der IOI kein Patient das Krankenhaus.

Schreibe ein Programm, das anhand der Anzahl der Bezirke und der Informationen über Krankenhäuser und Hitzschlagpatienten die maximale Anzahl von Patienten berechnet, die im obigen Szenario per Hubschrauber transportiert werden.

Eingabe

Lies die folgenden Daten aus der Standardeingabe.

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

Ausgabe

Schreibe eine Zeile in die Standardausgabe. Die Ausgabe soll die maximale Anzahl von Patienten enthalten, die per Hubschrauber transportiert werden.

Beschränkungen

• $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$).
• Alle gegebenen Werte sind ganze Zahlen.

Teilaufgaben

1. (6 Punkte) $X_1\le X_2\le\cdots\le X_N$.
2. (7 Punkte) $L\le 18$, $N\le 18$, $C_i=1$ ($1\le i\le L$).
3. (7 Punkte) $L\le 18$, $N\le 100$, $C_i=1$ ($1\le i\le L$).
4. (25 Punkte) $L\le 100$, $N\le 100$, $C_i=1$ ($1\le i\le L$).
5. (25 Punkte) $L\le 100$, $N\le 100$.
6. (10 Punkte) $L\le 600$, $N\le 600$.
7. (15 Punkte) $L\le 3\,500$, $N\le 3\,500$.
8. (5 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

3
1 1 1
3
1 2 2

Ausgabe 1

1

Hinweis

Im folgenden Fall wird 1 Patient per Hubschrauber transportiert.

1. Der 1. Patient wird in das Krankenhaus in Bezirk 2 gebracht. Dann beträgt die Anzahl der Patienten in den Krankenhäusern der Bezirke 1, 2, 3 jeweils 0, 1, 0.
2. Der 2. Patient wird in das Krankenhaus in Bezirk 3 gebracht. Dann beträgt die Anzahl der Patienten in den Krankenhäusern der Bezirke 1, 2, 3 jeweils 0, 1, 1.
3. Da für den 3. Patienten beide Krankenhäuser in den Bezirken 2 und 3 voll sind, wird er per Hubschrauber in ein allgemeines Krankenhaus außerhalb der Insel gebracht.

Da es keinen Fall gibt, in dem 2 oder mehr Patienten per Hubschrauber transportiert werden, gib 1 aus.

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 1, 2, 3, 4, 5, 6, 7, 8.

Eingabe 2

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

Ausgabe 2

3

Hinweis

Im folgenden Fall werden 3 Patienten per Hubschrauber transportiert.

1. Der 1. Patient wird in das Krankenhaus in Bezirk 2 gebracht. Dann beträgt die Anzahl der Patienten in den Krankenhäusern der Bezirke 1, 2, 3, 4, 5, 6 jeweils 0, 1, 0, 0, 0, 0.
2. Der 2. Patient wird in das Krankenhaus in Bezirk 4 gebracht. Dann beträgt die Anzahl der Patienten in den Krankenhäusern der Bezirke 1, 2, 3, 4, 5, 6 jeweils 0, 1, 0, 1, 0, 0.
3. Der 3. Patient wird in das Krankenhaus in Bezirk 5 gebracht. Dann beträgt die Anzahl der Patienten in den Krankenhäusern der Bezirke 1, 2, 3, 4, 5, 6 jeweils 0, 1, 0, 1, 1, 0.
4. Da für den 4. Patienten beide Krankenhäuser in den Bezirken 4 und 5 voll sind, wird er per Hubschrauber in ein allgemeines Krankenhaus außerhalb der Insel gebracht.
5. Der 5. Patient wird in das Krankenhaus in Bezirk 3 gebracht. Dann beträgt die Anzahl der Patienten in den Krankenhäusern der Bezirke 1, 2, 3, 4, 5, 6 jeweils 0, 1, 1, 1, 1, 0.
6. Da für den 6. Patienten beide Krankenhäuser in den Bezirken 2 und 3 voll sind, wird er per Hubschrauber in ein allgemeines Krankenhaus außerhalb der Insel gebracht.
7. Da für den 7. Patienten beide Krankenhäuser in den Bezirken 3 und 4 voll sind, wird er per Hubschrauber in ein allgemeines Krankenhaus außerhalb der Insel gebracht.

Da es keinen Fall gibt, in dem 4 oder mehr Patienten per Hubschrauber transportiert werden, gib 3 aus.

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 2, 3, 4, 5, 6, 7, 8.

Eingabe 3

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

Ausgabe 3

1

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 1, 5, 6, 7, 8.

Eingabe 4

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

Ausgabe 4

2

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 5, 6, 7, 8.

Eingabe 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

Ausgabe 5

3

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 5, 6, 7, 8.