Farmer John רוצה להרכיב תמונה פנורמית של שורת $N$ הפרות שלו ($(1 \le N \le 200,000)$), הממוספרות כרגיל מ־$1..N$. הוא צילם $M$ תמונות ($(1 \le M \le 100,000)$), כל אחת מכסה טווח רציף: תמונה $i$ מכילה את פרות $a_i$ עד $b_i$ כולל. יחד התמונות אינן בהכרח מכסות כל פרה.

FJ מגלה שבכל תמונה יש בדיוק פרה מנומרת אחת! הוא ידע שיש כאלה בעדר אך מעולם לא ספר אותן. לפי התמונות מצאו את המספר המרבי האפשרי של פרות מנומרות. אם אי אפשר להקצות כתמים לפרות באופן התואם את כל התמונות, הדפיסו $-1$.

קלט

• שורה $1$: השלמים $N$ ו־$M$.

• שורות $2..M+1$: שורה $i+1$ מכילה $a_i$ ו־$b_i$.

פלט

• שורה $1$: המספר המרבי האפשרי של פרות מנומרות, או $-1$ אם אין פתרון.

דוגמאות

קלט 1

5 3
1 4
2 5
3 4

פלט 1

1

Note

יש $5$ פרות ו־$3$ תמונות. הראשונה מכילה פרות $1$ עד $4$ וכן הלאה.

האחרונה מראה שפרה $3$ או $4$ חייבת להיות מנומרת. בחירת כל אחת מהן מקיימת גם את שתי התמונות הראשונות.

מחבר הבעיה: Brian Dean, 2013