בעיה

ברחוב הקניות JOI מפעילים שירות של כרטיסי נקודות. בכל כרטיס נקודות יש $2N$ משבצות. כאשר רוכשים מוצר ניתן להגריל גורל, ובהתאם לתוצאה מוטבעת במשבצת חותמת של "זכייה" או "הפסד". לא מוטבעת חותמת $2$ פעמים באותה משבצת. כרטיס נקודות שבו מוטבעת חותמת זכייה ב-$N$ משבצות או יותר מתוך $2N$ המשבצות ניתן להחלפה בפרס. בנוסף, ניתן לשנות חותמת בכרטיס נקודות תמורת $1$ ין עבור כל $1$ משבצת.

ל-JOI-kun יש $M$ כרטיסי נקודות שבהם כל $2N$ המשבצות מלאות. בכרטיס נקודות $i$ ($1 \le i \le M$) מוטבעות $A_i$ חותמות זכייה ו-$B_i$ חותמות הפסד. JOI-kun רוצה לפחות $M - 1$ פרסים.

מצאו את העלות המינימלית הדרושה כדי ש-JOI-kun ישיג לפחות $M - 1$ פרסים.

קלט

הקלט מורכב מ-$M + 1$ שורות.

בשורה $1$ כתובים $2$ מספרים שלמים $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) המופרדים ברווח. הדבר מציין שבכרטיס נקודות יש $2N$ משבצות ושל-JOI-kun יש $M$ כרטיסי נקודות.

בשורה ה-$i$ ($1 \le i \le M$) מתוך $M$ השורות הבאות כתובים $2$ מספרים שלמים $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), המציינים שבכרטיס נקודות $i$ מוטבעות $A_i$ חותמות זכייה ו-$B_i$ חותמות הפסד.

פלט

הדפיסו ב-$1$ שורה את העלות המינימלית הדרושה כדי ש-JOI-kun ישיג לפחות $M - 1$ פרסים.

דוגמאות קלט ופלט

קלט לדוגמה 1

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

פלט לדוגמה 1

4

קלט לדוגמה 2

5 4
5 5
8 2
3 7
8 2

פלט לדוגמה 2

0

בקלט לדוגמה 1, אם משנים בכרטיס נקודות $1$ בדיוק $3$ חותמות הפסד לחותמות זכייה, ובכרטיס נקודות $3$ משנים $1$ חותמת הפסד לחותמת זכייה, אז תמורת $4$ ין ניתן להחליף $4$ ($= 5 - 1$) כרטיסים בפרסים, וזוהי העלות המינימלית.

בקלט לדוגמה 2, מכיוון שכבר ניתן להחליף $3$ ($= 4 - 1$) כרטיסים בפרסים, אין צורך לשנות אף חותמת.