Đảo JOI gồm $L$ khu vực, được đánh số từ $1$ đến $L$ theo thứ tự từ tây sang đông. Trên đảo có $L-1$ con đường, được đánh số từ $1$ đến $L-1$. Đường $i$ ($1 \le i \le L-1$) nối hai khu vực $i$ và $i+1$ theo hai chiều.

Hiện tại, Kỳ thi Olympic Tin học Quốc tế (IOI 20XX) dự kiến được tổ chức trên Đảo JOI! Điều đáng lo ngại là hòn đảo nổi tiếng vì khí hậu cực kỳ nóng. Nguy cơ sốc nhiệt rất cao, đặc biệt đối với các thí sinh nước ngoài chưa quen với môi trường nóng bức. Vì vậy, ban tổ chức IOI quyết định thực hiện các biện pháp sau:

• Trước tiên, với mỗi $i$ ($1 \le i \le L$), họ chuẩn bị một bệnh viện tại khu vực $i$ có sức chứa $C_i$ người. Lưu ý rằng có thể có trường hợp $C_i=0$.
• Trong thời gian diễn ra IOI, khi một người trên đường $x$ ($1 \le x \le L-1$) bị sốc nhiệt, họ đưa người đó đến bệnh viện theo quy trình sau:
  • Đưa bệnh nhân đến bệnh viện tại khu vực $x$ hoặc $x+1$, chọn bệnh viện chưa đầy. Nếu cả hai bệnh viện đều chưa đầy, có thể chọn bất kỳ bệnh viện nào trong hai bệnh viện đó. Nếu cả hai bệnh viện đều đã đầy, họ đưa bệnh nhân đến một bệnh viện đa khoa ngoài đảo bằng trực thăng.

Vì sử dụng trực thăng rất tốn kém, ban tổ chức muốn ước tính số bệnh nhân tối đa phải vận chuyển bằng trực thăng. Họ xét tình huống sau làm ví dụ:

• Trước khi IOI diễn ra, không có bệnh nhân nào trong bất kỳ bệnh viện nào.
• Trong thời gian diễn ra IOI, $N$ người trên Đảo JOI sẽ bị sốc nhiệt. Bệnh nhân thứ $j$ ($1 \le j \le N$) xuất hiện trên đường $X_j$.
• Với mỗi $j$ ($1 \le j \le N-1$), khi bệnh nhân thứ $(j+1)$ bị sốc nhiệt, bệnh nhân thứ $j$ và tất cả bệnh nhân trước đó đều đã được đưa đến bệnh viện. Do các triệu chứng sốc nhiệt nghiêm trọng, không có bệnh nhân nào xuất viện trong thời gian diễn ra IOI.

Hãy viết chương trình, khi được cho số khu vực và thông tin về các bệnh viện cùng bệnh nhân sốc nhiệt, tính số bệnh nhân tối đa phải vận chuyển bằng trực thăng trong tình huống trên.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

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

Dữ liệu ra

Ghi một dòng ra đầu ra chuẩn. Dòng này phải chứa số bệnh nhân tối đa phải vận chuyển bằng trực thăng.

Giới hạ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$).
• Tất cả các giá trị đã cho đều là số nguyên.

Nhiệm vụ con

1. (6 điểm) $X_1 \le X_2 \le \cdots \le X_N$.
2. (7 điểm) $L \le 18$, $N \le 18$, $C_i=1$ ($1 \le i \le L$).
3. (7 điểm) $L \le 18$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
4. (25 điểm) $L \le 100$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
5. (25 điểm) $L \le 100$, $N \le 100$.
6. (10 điểm) $L \le 600$, $N \le 600$.
7. (15 điểm) $L \le 3\,500$, $N \le 3\,500$.
8. (5 điểm) Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

3
1 1 1
3
1 2 2

Dữ liệu ra 1

1

Ghi chú

Nếu diễn ra trường hợp sau, $1$ bệnh nhân sẽ được vận chuyển bằng trực thăng.

1. Đưa bệnh nhân thứ nhất đến bệnh viện tại khu vực $2$. Khi đó, số bệnh nhân trong bệnh viện tại các khu vực $1,2,3$ lần lượt là $0,1,0$.
2. Đưa bệnh nhân thứ hai đến bệnh viện tại khu vực $3$. Khi đó, số bệnh nhân trong bệnh viện tại các khu vực $1,2,3$ lần lượt là $0,1,1$.
3. Đối với bệnh nhân thứ ba, vì cả hai bệnh viện tại khu vực $2$ và $3$ đều đã đầy, đưa bệnh nhân đến một bệnh viện đa khoa ngoài đảo bằng trực thăng.

Vì không có trường hợp nào có từ $2$ bệnh nhân trở lên được vận chuyển bằng trực thăng, xuất $1$.

Dữ liệu vào của ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $1,2,3,4,5,6,7,8$.

Dữ liệu vào 2

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

Dữ liệu ra 2

3

Ghi chú

Nếu diễn ra trường hợp sau, $3$ bệnh nhân sẽ được vận chuyển bằng trực thăng.

1. Đưa bệnh nhân thứ nhất đến bệnh viện tại khu vực $2$. Khi đó, số bệnh nhân trong bệnh viện tại các khu vực $1,2,3,4,5,6$ lần lượt là $0,1,0,0,0,0$.
2. Đưa bệnh nhân thứ hai đến bệnh viện tại khu vực $4$. Khi đó, số bệnh nhân trong bệnh viện tại các khu vực $1,2,3,4,5,6$ lần lượt là $0,1,0,1,0,0$.
3. Đưa bệnh nhân thứ ba đến bệnh viện tại khu vực $5$. Khi đó, số bệnh nhân trong bệnh viện tại các khu vực $1,2,3,4,5,6$ lần lượt là $0,1,0,1,1,0$.
4. Đối với bệnh nhân thứ tư, vì cả hai bệnh viện tại khu vực $4$ và $5$ đều đã đầy, đưa bệnh nhân đến một bệnh viện đa khoa ngoài đảo bằng trực thăng.
5. Đưa bệnh nhân thứ năm đến bệnh viện tại khu vực $3$. Khi đó, số bệnh nhân trong bệnh viện tại các khu vực $1,2,3,4,5,6$ lần lượt là $0,1,1,1,1,0$.
6. Đối với bệnh nhân thứ sáu, vì cả hai bệnh viện tại khu vực $2$ và $3$ đều đã đầy, đưa bệnh nhân đến một bệnh viện đa khoa ngoài đảo bằng trực thăng.
7. Đối với bệnh nhân thứ bảy, vì cả hai bệnh viện tại khu vực $3$ và $4$ đều đã đầy, đưa bệnh nhân đến một bệnh viện đa khoa ngoài đảo bằng trực thăng.

Vì không có trường hợp nào có từ $4$ bệnh nhân trở lên được vận chuyển bằng trực thăng, xuất $3$.

Dữ liệu vào của ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $2,3,4,5,6,7,8$.

Dữ liệu vào 3

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

Dữ liệu ra 3

1

Ghi chú

Dữ liệu vào của ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $1,5,6,7,8$.

Dữ liệu vào 4

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

Dữ liệu ra 4

2

Ghi chú

Dữ liệu vào của ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $5,6,7,8$.

Dữ liệu vào 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

Dữ liệu ra 5

3

Ghi chú

Dữ liệu vào của ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $5,6,7,8$.