Problem F
Handkäs and Mispelchen

A traditional Mispelchen is made by mixing a loquat (or sometimes medlar) with 2cl of calvados.

You want to enjoy a traditional night out in Frankfurt with your friends. This involves a good meal of Handkäs mit Musik followed by a Mispelchen as a digestif. Sadly, no single pub may have sufficient food or drink to serve the entire group, so you may have to switch pubs. As a matter of decorum, nobody can start their mispelchen before everyone has had their meal.

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

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

A group of six friends can visit first the Schöne Müllerin and then switch to Kanonensteppel, so that everybody has had their handkäs. Then, still at the Kanonensteppel, a single person can now have a mispelchen. From there, the group has to switch places three more times (for instance, to Friedberger Warte, Eichkatzerl, and Zum Lemp) to find sufficient mispelchen. This took a total of four switches. There is a better way of doing it, requiring only three switches: Schöne Müllerin, Eichkatzerl, Friedberger Warte, and back to Schöne Müllerin.

How many times do you and your friends have to switch pubs before everyone has had both a handkäs and a mispelchen?

Input

The first line includes the number $n$ of friends (including you) and the number $k$ of pubs, with $1 \leq n \leq 100$ and $1 \leq k \leq 500$. Then follow $k$ lines, one for each pub. The $i$th line contains the number $h_ i$ of handkäs and the number $m_ i$ of mispelchen available at the $i$th pub, with $0\leq h_ i\leq 100$, $0\leq m_ i\leq 100$, $h_1+\cdots + h_ k\geq n$, and $m_1+\cdots + m_ k\geq n$.

Output

Output the smallest number of required switches.

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