JOI Island は $L$ 個の地区からなり，西から東へ $1$ から $L$ までの番号が付けられている．島には $L-1$ 本の道路があり，$1$ から $L-1$ までの番号が付けられている．道路 $i$ ($1 \le i \le L-1$) は地区 $i$ と地区 $i+1$ を双方向に結んでいる．

さて，JOI Island で国際情報オリンピック (IOI 20XX) が開催される予定である！懸念されるのは，この島が非常に暑いことで有名な点である．特に，暑い環境に慣れていない外国からの選手は，熱中症になる危険が高い．そこで，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{gathered} L\\ C_1\ C_2\ \cdots\ C_L\\ N\\ X_1\ X_2\ \cdots\ X_N \end{gathered} $$

出力

標準出力に 1 行で出力せよ．ヘリコプターによって搬送される患者数の最大値を出力せよ．

制約

• $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 の制約を満たす．