Problembeschreibung

Die JOI-Einkaufsstraße bietet einen Punktekarten-Service an. Jede Punktekarte hat $2N$ Felder. Wenn man einen Artikel kauft, darf man ein Los ziehen, und je nach Ergebnis wird ein Stempel für „Treffer“ oder „Niete“ in ein Feld gedruckt. Dasselbe Feld wird niemals $2$-mal abgestempelt. Eine Punktekarte, bei der auf mindestens $N$ der $2N$ Felder ein Treffer-Stempel steht, kann gegen eine Prämie eingetauscht werden. Außerdem kann man den Stempel auf einer Punktekarte für $1$ Yen pro $1$ Feld umschreiben lassen.

JOI-kun besitzt $M$ Punktekarten, bei denen alle $2N$ Felder ausgefüllt sind. Auf Punktekarte $i$ ($1 \le i \le M$) sind $A_i$ Treffer-Stempel und $B_i$ Nieten-Stempel aufgedruckt. JOI-kun möchte mindestens $M - 1$ Prämien erhalten.

Bestimme die minimalen Kosten, die erforderlich sind, damit JOI-kun mindestens $M - 1$ Prämien erhält.

Eingabe

Die Eingabe besteht aus $M + 1$ Zeilen.

In Zeile $1$ stehen $2$ durch ein Leerzeichen getrennte ganze Zahlen $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$). Dies bedeutet, dass jede Punktekarte $2N$ Felder hat und JOI-kun $M$ Punktekarten besitzt.

In der $i$-ten Zeile ($1 \le i \le M$) der folgenden $M$ Zeilen stehen jeweils $2$ ganze Zahlen $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), was bedeutet, dass auf Punktekarte $i$ genau $A_i$ Treffer-Stempel und $B_i$ Nieten-Stempel aufgedruckt sind.

Ausgabe

Gib die minimalen Kosten, die erforderlich sind, damit JOI-kun mindestens $M - 1$ Prämien erhält, in $1$ Zeile aus.

Beispiele

Eingabebeispiel 1

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

Ausgabebeispiel 1

4

Eingabebeispiel 2

5 4
5 5
8 2
3 7
8 2

Ausgabebeispiel 2

0

Im Eingabebeispiel 1 können für $4$ Yen genau $4$ ($= 5 - 1$) Karten gegen eine Prämie eingetauscht werden, wenn man auf Punktekarte $1$ genau $3$ Nieten-Stempel in Treffer-Stempel umschreiben lässt und auf Punktekarte $3$ genau $1$ Nieten-Stempel in einen Treffer-Stempel umschreiben lässt; dies sind die minimalen Kosten.

Im Eingabebeispiel 2 können bereits $3$ ($= 4 - 1$) Karten gegen eine Prämie eingetauscht werden, sodass keine Stempel umgeschrieben werden müssen.