JOI 岛由 $L$ 个行政区组成，从西向东编号为 $1$ 到 $L$。岛上有 $L-1$ 条道路，编号为 $1$ 到 $L-1$。道路 $i$ ($1 \le i \le L-1$) 双向连接行政区 $i$ 和 $i+1$。

现在，国际信息学奥林匹克竞赛（IOI 20XX）计划在 JOI 岛举行！人们担心该岛以极端高温而闻名。中暑的风险很高，特别是对于不适应炎热环境的外国参赛者。因此，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 活动期间没有病人离开医院。

编写一个程序，在给定行政区数量、医院信息和中暑病人信息的情况下，计算在上述场景中通过直升机运送的病人的最大数量。

输入格式

从标准输入读取以下数据：

$L$ $C_1 \ C_2 \ \dots \ C_L$ $N$ $X_1 \ X_2 \ \dots \ X_N$

输出格式

向标准输出写入一行。输出应包含通过直升机运送的病人的最大数量。

数据范围

• $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 \dots \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

样例输入 2

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

样例输出 2

3

样例输入 3

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

样例输出 3

1

样例输入 4

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

样例输出 4

2

样例输入 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