Problem F
Handkäs og mispelchen

En traditionel mispelchen består af en japansk mispel, 2 cl calvados og en tandstik.

En traditionel bytur i Frankfurt består af et godt måltid med Handkäs mit Musik efterfulgt af den hessiske brændevin Mispelchen som digestiv. Desværre har et enkelt værtshus ikke nødvendigvis nok med mad eller drikke til at betjene hele din vennegruppe, så I må muligvis skifte værtshus i løbet af aftenen. Almindelig pli foreskriver, at ingen kan nyde deres mispelchen, inden alle har spist.

Antag for eksempel, at antallet $h$ af handkäs og antallet $m$ af mispelchen på forskellige værtshuse i Frankfurt ser sådan ud:

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

En gruppe på seks venner kan først besøge Schöne Müllerin og derefter skifte til Kanonensteppel, så alle har fået deres handkäs. Derefter, stadig på Kanonensteppel, kan en enkelt person nu få en mispelchen. Derfra skal gruppen skifte værtshus tre gange mere (fx til Friedberger Warte, Eichkatzerl og Zum Lemp) for at finde tilstrækkelige mispelchen. Dette tog i alt fire skift. Der er en bedre måde at gøre det på, der kun kræver tre skift: Schöne Müllerin, Eichkatzerl, Friedberger Warte og tilbage til Schöne Müllerin.

Hvor mange gange skal du og dine venner skifte værtshus, før alle har fået både handkäs og mispelchen?

Input

På første linje står antallet $n$ af venner (inklusive dig selv) og antallet $k$ af værtshuse, hvor $1 \leq n \leq 100$ og $1 \leq k \leq 500$. Derefter følger $k$ linjer. Linje $i$ indeholder antallet $h_ i$ af handkäs og antallet $m_ i$ af mispelchen, som kan fås på det $i$te værtshus, hvor $0\leq h_ i\leq 100$, $0\leq m_ i\leq 100$, $h_1+\cdots + h_ k\geq n$ og $m_1+\cdots + m_ k\geq n$.

Output

Udskriv det mindste antal nødvendige skift.

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