Statement

JOI Island consists of $L$ districts, numbered from $1$ to $L$ from west to east. There are $L − 1$ roads in the island, numbered from $1$ to $L − 1$. Road $i$ ($1 \le i \le L − 1$) connects districts $i$ and $i + 1$ bidirectionally.

Now, the International Olympiad in Informatics (IOI 20XX) is planned to be held in JOI Island! The concern is that the island is famous for its extreme heat. There is a high risk of heat stroke, especially for foreign contestants who are not acclimatized to hot environment. So the organizers of IOI decided to take the following measures:

• First, for each $i$ ($1 \le i \le L$), they prepare a hospital at district $i$ with capacity of $C_i$ people. Note that there are cases that $C_i = 0$.
• During the IOI event, when a person on road $x$ ($1 \le x \le L − 1$) gets heat stroke, they send to hospital in the following procedure:
  • They send the patient to the hospital of either district $x$ or $x + 1$, whichever is not full. If both hospitals are not full, either choice is possible. If both hospital are full, they send the patient to a general hospital outside the island by helicopter.

Since the usage of helicopter is costly, the organizers want to estimate the maximum number of patients to be sent by helicopter. They consider the following scenario as an example:

• Before the IOI event, there are no patients in any hospital.
• During the IOI event, $N$ people will get heat stroke in JOI Island. The $j$-th ($1 \le j \le N$) patient occurs on road $X_j$.
• For each $j$ ($1 \le j \le N − 1$), when the $( j + 1)$-th patient gets heat stroke, the $j$-th patient and earlier is already sent to hospital. Due to the severe symptoms of heat stroke, no patients leave hospital during the IOI event.

Write a program which, given the number of districts and the information of hospitals and heat stroke patients, computes the maximum number of patients to be sent by helicopter in the scenario above.

Input

Read the following data from the standard input.

$L$

$C_1 \enspace C_2 \cdots C_L$

$N$

$X_1 \enspace X_2 · · · X_N$

Output

Write one line to the standard output. The output should contain the maximum number of patients to be sent by helicopter.

Constraints

• $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$).
• Given values are all integers.

Subtasks

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) No additional constraints.

3
1 1 1
3
1 2 2

1

If the following case happens, $1$ patient will be sent by helicopter.

1. Send the 1st patient to the hospital at district 2. Then, the number of patients in hospital at district 1, 2, 3 will be 0, 1, 0, respectively.
2. Send the 2nd patient to the hospital at district 3. Then, the number of patients in hospital at district 1, 2, 3 will be 0, 1, 1, respectively.
3. For the 3rd patient, since both hospitals at district 2 and 3 are full, send the patient to a general hospital outside the island by helicopter.

Since there are no cases that $2$ or more patients will be sent by helicopter, output 1. This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 5, 6, 7, 8.

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

3

If the following case happens, $3$ patient will be sent by helicopter.

1. Send the 1st patient to the hospital at district 2. Then, the number of patients in hospital at district 1, 2, 3, 4, 5, 6 will be 0, 1, 0, 0, 0, 0, respectively.
2. Send the 2nd patient to the hospital at district 4. Then, the number of patients in hospital at district 1, 2, 3, 4, 5, 6 will be 0, 1, 0, 1, 0, 0, respectively.
3. Send the 3rd patient to the hospital at district 5. Then, the number of patients in hospital at district 1, 2, 3, 4, 5, 6 will be 0, 1, 0, 1, 1, 0, respectively.
4. For the 4th patient, since both hospitals at district 4 and 5 are full, send the patient to a general hospital outside the island by helicopter.
5. Send the 5th patient to the hospital at district 3. Then, the number of patients in hospital at district 1, 2, 3, 4, 5, 6 will be 0, 1, 1, 1, 1, 0, respectively.
6. For the 6th patient, since both hospitals at district 2 and 3 are full, send the patient to a general hospital outside the island by helicopter.
7. For the 7th patient, since both hospitals at district 3 and 4 are full, send the patient to a general hospital outside the island by helicopter.

Since there are no cases that $4$ or more patients will be sent by helicopter, output 3.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7, 8.

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

1

This sample input satisfies the constraints of Subtasks 1, 5, 6, 7, 8.

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

2

This sample input satisfies the constraints of Subtasks 5, 6, 7, 8.

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

3

This sample input satisfies the constraints of Subtasks 5, 6, 7, 8.