חורף בחווה, וזה אומר שלג! בשביל מהבית לאסם יש $N$ אריחים שמספריהם $1 \dots N$, ועל אריח $i$ יש שלג בעומק $f_i$ רגל.

Farmer John מתחיל באריח $1$ ועליו להגיע לאריח $N$ כדי להעיר את הפרות. אריח $1$ מוגן בגג הבית ואריח $N$ בגג האסם, ולכן אין שלג על שניהם. כדי לדרוך על האחרים הוא זקוק למגפיים!

בתרמיל למזג אוויר גרוע יש לו $B$ זוגות מגפיים שמספריהם $1 \dots B$. חלקם עמידים יותר וחלקם זריזים יותר. זוג $i$ מאפשר לדרוך בשלג בעומק לכל היותר $s_i$ רגל ולהתקדם לכל היותר $d_i$ אריחים בכל צעד.

למרבה הצער, האריזה מאפשרת גישה רק לזוג העליון בכל רגע. הוא יכול לנעול את הזוג העליון ולזרוק את הישן, או לזרוק את העליון כדי להגיע לזוג הבא.

אפשר להחליף מגפיים רק בעמידה על אריח. אם יש עליו שלג בעומק $f$ רגל, גם הזוג שהוא חולץ וגם הזוג שהוא נועל חייבים לעמוד בשלג בעומק לפחות $f$ רגל. זוגות ביניים שהוא זורק בלי לנעול אינם חייבים לעמוד בתנאי הזה.

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

קלט

השורה הראשונה מכילה את המספרים השלמים $N$ ו־$B$, המופרדים ברווח ($2 \leq N,B \leq 250$).

השורה השנייה מכילה $N$ מספרים שלמים המופרדים ברווחים. המספר במקום $i$ הוא $f_i$, עומק השלג באריח $i$ ($0 \leq f_i \leq 10^9$). מובטח ש־$f_1 = f_N = 0$.

$B$ השורות הבאות מכילות כל אחת שני מספרים שלמים המופרדים ברווח. הראשון בשורה $i+2$ הוא $s_i$, עומק השלג המרבי לזוג $i$. השני בשורה $i+2$ הוא $d_i$, אורך הצעד המרבי לזוג $i$. מובטח ש־$0 \leq s_i \leq 10^9$ וכן $1 \leq d_i \leq N-1$.

הזוגות מתוארים מלמעלה למטה, ולכן זוג $1$ נמצא בראש התרמיל, וכן הלאה.

פלט

הדפיסו מספר שלם אחד: המספר המזערי של זוגות שעליו לזרוק. מובטח שאפשר להגיע לאסם.

דוגמאות

קלט 1

10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1

פלט 1

2

מחברי הבעיה: Brian Dean ו־Dhruv Rohatgi