Problem F
Handkäs und Mispelchen

Ein Mispelchen beinhaltet traditionel eine japansiche Wollmispel, 2cl Calvados und einen Zahnstocher.

Du bist mit Freund:innen in Frankfurt unterwegs und ihr habt alle nur 2 Ansprüche an den Abend: Ihr wollt alle jeweils einen Handk"s mit Musik als Vorspeise und ein Mispelchen als Digestif haben. Es kann sein das man das Lokal wechseln muss, da es möglicherweise ein keinem Apfelweinlokal genug von beidem gibt. Nun würde niemand ihr/sein Mispelchen trinken, wenn nicht alle ihren Handkäs gegessen haben.

For instance, assume the number $h$ of handkäs and the number $m$ of mispelchen at various pubs in Frankfurt looks like this:

Apfelweinlokal	$h$	$m$
Schöne Müllerin	4	2
Eichkatzerl	2	2
Friedberger Warte	0	2
Zum Lemp	1	1
Kanonensteppel	3	1

Eine Gruppe bestehend aus sechs Freund:innen könnte also zuerst in die Schöne Müllerin dann zum Kanonensteppel, sodass jetzt jede:r schon mal Handkäs hatte. Dann, im Kanonensteppel bleibend, kann eine Person schon mal ihr Mispelchen trinken. Von hier aus muss die Gruppe dann noch dreimal das Lokal wechseln (z.B. Friedberger Warte, Eichkatzerl und Zum Lemp) für genügend Mispelchen. Das waren nun insgesamt $4$ Lokalwechsel. Es gibt allerdings auch eine Route, die nur $3$ Lokalwechsel benötigt.

Schöne Müllerin, Eichkatzerl, Friedberger Warte und zurück zur Schöne Müllerin.

Wie oft muss das Lokal mindestens gewechselt werden bevor alle fertig sind?

Input

Die erste Zeile beinhaltet die Anzahl $n$ an Freunden (inkl. dir) und die Anzahl $k$ an Apfelweinkneipen mit $1 \leq n \leq 100$ und $1 \leq k \leq 500$. Dann folgen $k$ Zeilen, eine pro Apfelweinkneipe. Die $i$te dieser Zeilen beinhaltet die Anzahl $h_ i$ an Handkäs und die Anzahl $m_ i$ an Mispelchen, die jeweils im $i$ten Lokal erhältlich sind, mit $0\leq h_ i\leq 100$, $0\leq m_ i\leq 100$, $h_1+\cdots + h_ k\geq n$ und $m_1+\cdots + m_ k\geq n$.

Output

Gib die Mindestanzahl an benötigten Kneipenwechseln an, die benötigt wird damit jede:r eine komplette Mahlzeit erhält.

6 5
4 2
2 2
0 2
1 1
3 1

3

1 2
1 0
0 1

1

1 2
1 1
0 0

0

100 3
50 50
49 49
1 1

4