Остров JOI состоит из $L$ районов, пронумерованных от $1$ до $L$ с запада на восток. На острове есть $L-1$ дорог, пронумерованных от $1$ до $L-1$. Дорога $i$ ($1\le i\le L-1$) соединяет районы $i$ и $i+1$ в обоих направлениях.

Район 1 — Дорога 1 — Район 2 — Дорога 2 — Район 3 — … — Район $L$.

На острове JOI планируется провести Международную олимпиаду по информатике (IOI 20XX)! Однако остров известен своей чрезвычайной жарой. Существует высокий риск теплового удара, особенно для иностранных участников, не привыкших к жаркому климату. Поэтому организаторы IOI решили принять следующие меры:

• Сначала для каждого $i$ ($1\le i\le L$) они подготавливают в районе $i$ больницу вместимостью $C_i$ человек. Возможны случаи, когда $C_i=0$.

• Во время IOI, когда человек на дороге $x$ ($1\le x\le L-1$) получает тепловой удар, его отправляют в больницу следующим образом:

  • Пациента отправляют в больницу района $x$ или $x+1$, в которой есть свободное место. Если свободные места есть в обеих больницах, можно выбрать любую из них. Если обе больницы заполнены, пациента отправляют вертолётом в многопрофильную больницу за пределами острова.

Поскольку использование вертолёта обходится дорого, организаторы хотят оценить максимальное количество пациентов, которых придётся отправить вертолётом. Для примера они рассматривают следующий сценарий:

• До начала IOI во всех больницах нет пациентов.
• Во время IOI тепловой удар на острове JOI получат $N$ человек. Пациент $j$ ($1\le j\le N$) появится на дороге $X_j$.
• Для каждого $j$ ($1\le j\le N-1$) к моменту, когда тепловой удар получает пациент $j+1$, пациент $j$ и все предыдущие пациенты уже отправлены в больницы. Из-за тяжести симптомов теплового удара ни один пациент не покидает больницу во время IOI.

Напишите программу, которая по количеству районов и информации о больницах и пациентах с тепловым ударом вычисляет максимальное количество пациентов, которых отправят вертолётом в описанном сценарии.

Входные данные

Прочитайте следующие данные из стандартного потока ввода.

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

Выходные данные

Выведите в стандартный поток вывода одну строку, содержащую максимальное количество пациентов, которых отправят вертолётом.

Ограничения

• $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$).
• Все заданные значения — целые числа.

Подзадачи

1. (6 баллов) $X_1\le X_2\le\cdots\le X_N$.
2. (7 баллов) $L\le18$, $N\le18$, $C_i=1$ ($1\le i\le L$).
3. (7 баллов) $L\le18$, $N\le100$, $C_i=1$ ($1\le i\le L$).
4. (25 баллов) $L\le100$, $N\le100$, $C_i=1$ ($1\le i\le L$).
5. (25 баллов) $L\le100$, $N\le100$.
6. (10 баллов) $L\le600$, $N\le600$.
7. (15 баллов) $L\le3\,500$, $N\le3\,500$.
8. (5 баллов) Дополнительных ограничений нет.

Примеры

Входные данные 1

3
1 1 1
3
1 2 2

Выходные данные 1

1

Примечание

В следующем случае $1$ пациент будет отправлен вертолётом.

1. Первого пациента отправляют в больницу района $2$. После этого количество пациентов в больницах районов $1,2,3$ равно соответственно $0,1,0$.
2. Второго пациента отправляют в больницу района $3$. После этого количество пациентов в больницах районов $1,2,3$ равно соответственно $0,1,1$.
3. Для третьего пациента обе больницы районов $2$ и $3$ заполнены, поэтому его отправляют вертолётом в многопрофильную больницу за пределами острова.

Поскольку невозможно отправить вертолётом $2$ или более пациентов, выведите 1.

Этот пример входных данных удовлетворяет ограничениям подзадач 1, 2, 3, 4, 5, 6, 7, 8.

Входные данные 2

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

Выходные данные 2

3

Примечание

В следующем случае $3$ пациента будут отправлены вертолётом.

1. Первого пациента отправляют в больницу района $2$. После этого количество пациентов в больницах районов $1,2,3,4,5,6$ равно соответственно $0,1,0,0,0,0$.
2. Второго пациента отправляют в больницу района $4$. После этого количество пациентов в больницах районов $1,2,3,4,5,6$ равно соответственно $0,1,0,1,0,0$.
3. Третьего пациента отправляют в больницу района $5$. После этого количество пациентов в больницах районов $1,2,3,4,5,6$ равно соответственно $0,1,0,1,1,0$.
4. Для четвёртого пациента обе больницы районов $4$ и $5$ заполнены, поэтому его отправляют вертолётом в многопрофильную больницу за пределами острова.
5. Пятого пациента отправляют в больницу района $3$. После этого количество пациентов в больницах районов $1,2,3,4,5,6$ равно соответственно $0,1,1,1,1,0$.
6. Для шестого пациента обе больницы районов $2$ и $3$ заполнены, поэтому его отправляют вертолётом в многопрофильную больницу за пределами острова.
7. Для седьмого пациента обе больницы районов $3$ и $4$ заполнены, поэтому его отправляют вертолётом в многопрофильную больницу за пределами острова.

Поскольку невозможно отправить вертолётом $4$ или более пациентов, выведите 3.

Этот пример входных данных удовлетворяет ограничениям подзадач 2, 3, 4, 5, 6, 7, 8.

Входные данные 3

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

Выходные данные 3

1

Примечание

Этот пример входных данных удовлетворяет ограничениям подзадач 1, 5, 6, 7, 8.

Входные данные 4

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

Выходные данные 4

2

Примечание

Этот пример входных данных удовлетворяет ограничениям подзадач 5, 6, 7, 8.

Входные данные 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

Выходные данные 5

3

Примечание

Этот пример входных данных удовлетворяет ограничениям подзадач 5, 6, 7, 8.