เกาะ 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

จงเขียนโปรแกรมที่รับจำนวนเขตและข้อมูลโรงพยาบาลกับผู้ป่วยลมแดด แล้วคำนวณจำนวนผู้ป่วยมากที่สุดที่จะถูกส่งด้วยเฮลิคอปเตอร์ในสถานการณ์ข้างต้น

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

$$ \begin{array}{l} 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