Pulau JOI terdiri dari $L$ distrik yang diberi nomor $1$ sampai $L$ dari barat ke timur. Terdapat $L-1$ jalan di pulau ini, bernomor $1$ sampai $L-1$. Jalan $i$ ($1 \le i \le L-1$) menghubungkan distrik $i$ dan $i+1$ dalam kedua arah.

Distrik $1$ — Jalan $1$ — Distrik $2$ — Jalan $2$ — Distrik $3$ — $\cdots$ — Distrik $L$

Kini International Olympiad in Informatics (IOI 20XX) direncanakan berlangsung di Pulau JOI! Yang menjadi kekhawatiran adalah pulau ini terkenal sangat panas. Risiko sengatan panas tinggi, terutama bagi peserta asing yang belum terbiasa dengan lingkungan panas. Oleh karena itu, penyelenggara IOI memutuskan mengambil langkah berikut:

• Pertama, untuk setiap $i$ ($1 \le i \le L$), mereka menyiapkan rumah sakit di distrik $i$ dengan kapasitas $C_i$ orang. Perhatikan bahwa $C_i$ bisa bernilai $0$.

• Selama acara IOI, ketika seseorang di jalan $x$ ($1 \le x \le L-1$) terkena sengatan panas, orang tersebut dikirim ke rumah sakit dengan prosedur berikut:

  • Pasien dikirim ke rumah sakit di distrik $x$ atau $x+1$ yang belum penuh. Jika keduanya belum penuh, boleh memilih salah satunya. Jika keduanya penuh, pasien dikirim dengan helikopter ke rumah sakit umum di luar pulau.

Karena penggunaan helikopter mahal, penyelenggara ingin memperkirakan jumlah maksimum pasien yang akan dikirim dengan helikopter. Mereka mempertimbangkan skenario berikut sebagai contoh:

• Sebelum acara IOI, tidak ada pasien di rumah sakit mana pun.
• Selama acara IOI, $N$ orang akan terkena sengatan panas di Pulau JOI. Pasien ke-$j$ ($1 \le j \le N$) berada di jalan $X_j$.
• Untuk setiap $j$ ($1 \le j \le N-1$), ketika pasien ke-$(j+1)$ terkena sengatan panas, pasien ke-$j$ dan semua pasien sebelumnya sudah dikirim ke rumah sakit. Karena gejala sengatan panas yang parah, tidak ada pasien yang keluar dari rumah sakit selama acara IOI.

Tulislah program yang, diberikan jumlah distrik serta informasi tentang rumah sakit dan pasien sengatan panas, menghitung jumlah maksimum pasien yang akan dikirim dengan helikopter dalam skenario di atas.

Masukan

Baca data berikut dari masukan standar.

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

Keluaran

Tuliskan satu baris ke keluaran standar yang berisi jumlah maksimum pasien yang akan dikirim dengan helikopter.

Batasan

• $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$).
• Semua nilai yang diberikan adalah bilangan bulat.

Subtugas

1. (6 poin) $X_1 \le X_2 \le \cdots \le X_N$.
2. (7 poin) $L \le 18$, $N \le 18$, $C_i=1$ ($1 \le i \le L$).
3. (7 poin) $L \le 18$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
4. (25 poin) $L \le 100$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
5. (25 poin) $L \le 100$, $N \le 100$.
6. (10 poin) $L \le 600$, $N \le 600$.
7. (15 poin) $L \le 3\,500$, $N \le 3\,500$.
8. (5 poin) Tidak ada batasan tambahan.

Contoh

Masukan 1

3
1 1 1
3
1 2 2

Keluaran 1

1

Penjelasan

Jika hal berikut terjadi, $1$ pasien akan dikirim dengan helikopter.

1. Kirim pasien pertama ke rumah sakit di distrik $2$. Jumlah pasien di rumah sakit distrik $1,2,3$ kemudian berturut-turut menjadi $0,1,0$.
2. Kirim pasien kedua ke rumah sakit di distrik $3$. Jumlah pasien di rumah sakit distrik $1,2,3$ kemudian berturut-turut menjadi $0,1,1$.
3. Untuk pasien ketiga, karena rumah sakit di distrik $2$ dan $3$ sama-sama penuh, kirim pasien dengan helikopter ke rumah sakit umum di luar pulau.

Karena tidak ada kemungkinan $2$ pasien atau lebih dikirim dengan helikopter, keluarkan $1$.

Contoh ini memenuhi batasan subtugas $1,2,3,4,5,6,7,8$.

Masukan 2

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

Keluaran 2

3

Penjelasan

Jika hal berikut terjadi, $3$ pasien akan dikirim dengan helikopter.

1. Kirim pasien pertama ke rumah sakit di distrik $2$. Jumlah pasien di rumah sakit distrik $1,2,3,4,5,6$ kemudian berturut-turut menjadi $0,1,0,0,0,0$.
2. Kirim pasien kedua ke rumah sakit di distrik $4$. Jumlah pasien di rumah sakit distrik $1,2,3,4,5,6$ kemudian berturut-turut menjadi $0,1,0,1,0,0$.
3. Kirim pasien ketiga ke rumah sakit di distrik $5$. Jumlah pasien di rumah sakit distrik $1,2,3,4,5,6$ kemudian berturut-turut menjadi $0,1,0,1,1,0$.
4. Untuk pasien keempat, karena rumah sakit di distrik $4$ dan $5$ sama-sama penuh, kirim pasien dengan helikopter ke rumah sakit umum di luar pulau.
5. Kirim pasien kelima ke rumah sakit di distrik $3$. Jumlah pasien di rumah sakit distrik $1,2,3,4,5,6$ kemudian berturut-turut menjadi $0,1,1,1,1,0$.
6. Untuk pasien keenam, karena rumah sakit di distrik $2$ dan $3$ sama-sama penuh, kirim pasien dengan helikopter ke rumah sakit umum di luar pulau.
7. Untuk pasien ketujuh, karena rumah sakit di distrik $3$ dan $4$ sama-sama penuh, kirim pasien dengan helikopter ke rumah sakit umum di luar pulau.

Karena tidak ada kemungkinan $4$ pasien atau lebih dikirim dengan helikopter, keluarkan $3$.

Contoh ini memenuhi batasan subtugas $2,3,4,5,6,7,8$.

Masukan 3

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

Keluaran 3

1

Contoh ini memenuhi batasan subtugas $1,5,6,7,8$.

Masukan 4

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

Keluaran 4

2

Contoh ini memenuhi batasan subtugas $5,6,7,8$.

Masukan 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

Keluaran 5

3

Contoh ini memenuhi batasan subtugas $5,6,7,8$.