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 活動期間，JOI Island 上會有 $N$ 人中暑。第 $j$ 位病人（$1\le j\le N$）發生在道路 $X_j$。
• 對每個 $j$（$1\le j\le N-1$），第 $j+1$ 位病人中暑時，第 $j$ 位及更早的病人都已送往醫院。由於中暑症狀嚴重，IOI 活動期間不會有病人出院。

請撰寫程式，根據地區數量、醫院及中暑病人的資訊，計算上述情境中最多可能有多少位病人以直升機運送。

輸入格式

從標準輸入讀取以下資料。

$$ \begin{array}{llll} 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 的限制。