האי 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, $N$ אנשים באי JOI Island ילקו במכת חום. החולה ה-$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} $$

פלט

כתבו שורה אחת לפלט הסטנדרטי. עליה להכיל את המספר המרבי של חולים שיפונו במסוק.

מגבלות

• $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. מפנים את החולה הראשון לבית החולים במחוז $2$. אז מספרי החולים בבתי החולים במחוזות $1,2,3$ יהיו $0,1,0$, בהתאמה.
2. מפנים את החולה השני לבית החולים במחוז $3$. אז מספרי החולים בבתי החולים במחוזות $1,2,3$ יהיו $0,1,1$, בהתאמה.
3. עבור החולה השלישי, מכיוון ששני בתי החולים במחוזות $2$ ו-$3$ מלאים, מפנים אותו במסוק לבית חולים כללי מחוץ לאי.

מכיוון שאין מצב שבו יפונו במסוק שני חולים או יותר, יש להדפיס $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

הסבר

אם מתרחש המצב הבא, שלושה חולים יפונו במסוק.

1. מפנים את החולה הראשון לבית החולים במחוז $2$. אז מספרי החולים בבתי החולים במחוזות $1,2,3,4,5,6$ יהיו $0,1,0,0,0,0$, בהתאמה.
2. מפנים את החולה השני לבית החולים במחוז $4$. אז מספרי החולים בבתי החולים במחוזות $1,2,3,4,5,6$ יהיו $0,1,0,1,0,0$, בהתאמה.
3. מפנים את החולה השלישי לבית החולים במחוז $5$. אז מספרי החולים בבתי החולים במחוזות $1,2,3,4,5,6$ יהיו $0,1,0,1,1,0$, בהתאמה.
4. עבור החולה הרביעי, מכיוון ששני בתי החולים במחוזות $4$ ו-$5$ מלאים, מפנים אותו במסוק לבית חולים כללי מחוץ לאי.
5. מפנים את החולה החמישי לבית החולים במחוז $3$. אז מספרי החולים בבתי החולים במחוזות $1,2,3,4,5,6$ יהיו $0,1,1,1,1,0$, בהתאמה.
6. עבור החולה השישי, מכיוון ששני בתי החולים במחוזות $2$ ו-$3$ מלאים, מפנים אותו במסוק לבית חולים כללי מחוץ לאי.
7. עבור החולה השביעי, מכיוון ששני בתי החולים במחוזות $3$ ו-$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.