Wyspa JOI składa się z $L$ dzielnic, ponumerowanych od $1$ do $L$ z zachodu na wschód. Na wyspie znajduje się $L-1$ dróg, ponumerowanych od $1$ do $L-1$. Droga $i$ ($1 \le i \le L-1$) łączy dzielnice $i$ oraz $i+1$ w obu kierunkach.

Na wyspie JOI ma się odbyć Międzynarodowa Olimpiada Informatyczna (IOI 20XX)! Problem w tym, że wyspa słynie z niezwykłych upałów. Ryzyko udaru cieplnego jest wysokie, zwłaszcza wśród zagranicznych zawodników, którzy nie są przyzwyczajeni do gorącego klimatu. Organizatorzy IOI postanowili więc podjąć następujące działania:

• Najpierw dla każdego $i$ ($1 \le i \le L$) przygotowują w dzielnicy $i$ szpital mieszczący $C_i$ osób. Należy pamiętać, że może być $C_i=0$.

• Gdy podczas IOI osoba znajdująca się na drodze $x$ ($1 \le x \le L-1$) dozna udaru cieplnego, zostaje przewieziona do szpitala zgodnie z następującą procedurą:

  • Pacjent zostaje przewieziony do szpitala w dzielnicy $x$ lub $x+1$, w którym są wolne miejsca. Jeśli w obu szpitalach są wolne miejsca, można wybrać dowolny z nich. Jeśli oba szpitale są pełne, pacjent zostaje przewieziony helikopterem do szpitala ogólnego poza wyspą.

Ponieważ korzystanie z helikoptera jest kosztowne, organizatorzy chcą oszacować maksymalną liczbę pacjentów, którzy zostaną przewiezieni helikopterem. Jako przykład rozważają następujący scenariusz:

• Przed rozpoczęciem IOI w żadnym szpitalu nie ma pacjentów.
• Podczas IOI na wyspie JOI udaru cieplnego dozna $N$ osób. $j$-ty pacjent ($1 \le j \le N$) pojawia się na drodze $X_j$.
• Dla każdego $j$ ($1 \le j \le N-1$), gdy udaru cieplnego dozna $(j+1)$-szy pacjent, $j$-ty pacjent i wszyscy wcześniejsi są już przewiezieni do szpitala. Ze względu na poważne objawy udaru cieplnego żaden pacjent nie opuści szpitala w trakcie IOI.

Napisz program, który na podstawie liczby dzielnic oraz informacji o szpitalach i pacjentach z udarem cieplnym obliczy maksymalną liczbę pacjentów przewiezionych helikopterem w powyższym scenariuszu.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

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

Wyjście

Wypisz jeden wiersz na standardowe wyjście. Powinien on zawierać maksymalną liczbę pacjentów przewiezionych helikopterem.

Ograniczenia

• $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$).
• Wszystkie podane wartości są liczbami całkowitymi.

Podzadania

1. ($6$ punktów) $X_1 \le X_2 \le \cdots \le X_N$.
2. ($7$ punktów) $L \le 18$, $N \le 18$, $C_i=1$ ($1 \le i \le L$).
3. ($7$ punktów) $L \le 18$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
4. ($25$ punktów) $L \le 100$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
5. ($25$ punktów) $L \le 100$, $N \le 100$.
6. ($10$ punktów) $L \le 600$, $N \le 600$.
7. ($15$ punktów) $L \le 3\,500$, $N \le 3\,500$.
8. ($5$ punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

3
1 1 1
3
1 2 2

Wyjście 1

1

Uwagi

Jeśli wydarzy się poniższa sytuacja, jeden pacjent zostanie przewieziony helikopterem.

1. Pierwszy pacjent zostaje przewieziony do szpitala w dzielnicy $2$. Liczby pacjentów w szpitalach w dzielnicach $1,2,3$ wynoszą wtedy odpowiednio $0,1,0$.
2. Drugi pacjent zostaje przewieziony do szpitala w dzielnicy $3$. Liczby pacjentów w szpitalach w dzielnicach $1,2,3$ wynoszą wtedy odpowiednio $0,1,1$.
3. W przypadku trzeciego pacjenta oba szpitale w dzielnicach $2$ i $3$ są pełne, więc zostaje on przewieziony helikopterem do szpitala ogólnego poza wyspą.

Nie ma sytuacji, w której co najmniej dwóch pacjentów zostałoby przewiezionych helikopterem, więc wypisz $1$.

To przykładowe wejście spełnia ograniczenia podzadań $1,2,3,4,5,6,7,8$.

Wejście 2

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

Wyjście 2

3

Uwagi

Jeśli wydarzy się poniższa sytuacja, trzech pacjentów zostanie przewiezionych helikopterem.

1. Pierwszy pacjent zostaje przewieziony do szpitala w dzielnicy $2$. Liczby pacjentów w szpitalach w dzielnicach $1,2,3,4,5,6$ wynoszą wtedy odpowiednio $0,1,0,0,0,0$.
2. Drugi pacjent zostaje przewieziony do szpitala w dzielnicy $4$. Liczby pacjentów w szpitalach w dzielnicach $1,2,3,4,5,6$ wynoszą wtedy odpowiednio $0,1,0,1,0,0$.
3. Trzeci pacjent zostaje przewieziony do szpitala w dzielnicy $5$. Liczby pacjentów w szpitalach w dzielnicach $1,2,3,4,5,6$ wynoszą wtedy odpowiednio $0,1,0,1,1,0$.
4. W przypadku czwartego pacjenta oba szpitale w dzielnicach $4$ i $5$ są pełne, więc zostaje on przewieziony helikopterem do szpitala ogólnego poza wyspą.
5. Piąty pacjent zostaje przewieziony do szpitala w dzielnicy $3$. Liczby pacjentów w szpitalach w dzielnicach $1,2,3,4,5,6$ wynoszą wtedy odpowiednio $0,1,1,1,1,0$.
6. W przypadku szóstego pacjenta oba szpitale w dzielnicach $2$ i $3$ są pełne, więc zostaje on przewieziony helikopterem do szpitala ogólnego poza wyspą.
7. W przypadku siódmego pacjenta oba szpitale w dzielnicach $3$ i $4$ są pełne, więc zostaje on przewieziony helikopterem do szpitala ogólnego poza wyspą.

Nie ma sytuacji, w której co najmniej czterech pacjentów zostałoby przewiezionych helikopterem, więc wypisz $3$.

To przykładowe wejście spełnia ograniczenia podzadań $2,3,4,5,6,7,8$.

Wejście 3

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

Wyjście 3

1

Uwagi

To przykładowe wejście spełnia ograniczenia podzadań $1,5,6,7,8$.

Wejście 4

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

Wyjście 4

2

Uwagi

To przykładowe wejście spełnia ograniczenia podzadań $5,6,7,8$.

Wejście 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

Wyjście 5

3

Uwagi

To przykładowe wejście spełnia ograniczenia podzadań $5,6,7,8$.