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

Тепер Міжнародну олімпіаду з інформатики (IOI 20XX) планують провести на JOI Island! Занепокоєння викликає те, що острів відомий надзвичайною спекою. Існує високий ризик теплового удару, особливо для іноземних учасників, які не звикли до спекотного середовища. Тому організатори 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 $N$ людей на JOI Island зазнають теплового удару. Пацієнт із номером $j$ ($1\le j\le N$) з'являється на дорозі $X_j$.
• Для кожного $j$ ($1\le j\le N-1$), коли пацієнт із номером $j+1$ зазнає теплового удару, пацієнта з номером $j$ та всіх попередніх уже відправлено до лікарні. Через тяжкі симптоми теплового удару жоден пацієнт не залишає лікарню під час IOI.

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

Вхідні дані

Зчитайте такі дані зі стандартного вводу.

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

Вихідні дані

Виведіть один рядок у стандартний вивід. Він має містити максимальну кількість пацієнтів, яких відправлять вертольотом.

Обмеження

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

Підзадачі

1. (6 балів) $X_1\le X_2\le\cdots\le X_N$.
2. (7 балів) $L\le 18$, $N\le 18$, $C_i=1$ ($1\le i\le L$).
3. (7 балів) $L\le 18$, $N\le 100$, $C_i=1$ ($1\le i\le L$).
4. (25 балів) $L\le 100$, $N\le 100$, $C_i=1$ ($1\le i\le L$).
5. (25 балів) $L\le 100$, $N\le 100$.
6. (10 балів) $L\le 600$, $N\le 600$.
7. (15 балів) $L\le 3\,500$, $N\le 3\,500$.
8. (5 балів) Без додаткових обмежень.

Приклади

Вхідні дані 1

3
1 1 1
3
1 2 2

Вихідні дані 1

1

Примітка

У наступному випадку 1 пацієнта відправлять вертольотом.

1. Відправимо 1-го пацієнта до лікарні в районі 2. Тоді кількість пацієнтів у лікарнях районів 1, 2, 3 становитиме відповідно 0, 1, 0.
2. Відправимо 2-го пацієнта до лікарні в районі 3. Тоді кількість пацієнтів у лікарнях районів 1, 2, 3 становитиме відповідно 0, 1, 1.
3. Оскільки для 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. Відправимо 1-го пацієнта до лікарні в районі 2. Тоді кількість пацієнтів у лікарнях районів 1, 2, 3, 4, 5, 6 становитиме відповідно 0, 1, 0, 0, 0, 0.
2. Відправимо 2-го пацієнта до лікарні в районі 4. Тоді кількість пацієнтів у лікарнях районів 1, 2, 3, 4, 5, 6 становитиме відповідно 0, 1, 0, 1, 0, 0.
3. Відправимо 3-го пацієнта до лікарні в районі 5. Тоді кількість пацієнтів у лікарнях районів 1, 2, 3, 4, 5, 6 становитиме відповідно 0, 1, 0, 1, 1, 0.
4. Оскільки для 4-го пацієнта обидві лікарні в районах 4 та 5 заповнені, відправимо його вертольотом до лікарні загального профілю за межами острова.
5. Відправимо 5-го пацієнта до лікарні в районі 3. Тоді кількість пацієнтів у лікарнях районів 1, 2, 3, 4, 5, 6 становитиме відповідно 0, 1, 1, 1, 1, 0.
6. Оскільки для 6-го пацієнта обидві лікарні в районах 2 та 3 заповнені, відправимо його вертольотом до лікарні загального профілю за межами острова.
7. Оскільки для 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.