Problem F
Blaðra

Blöðrur

In Forritunarkeppni Framhaldsskólanna all teams get a balloon for each problem they solve, the balloons being different colours depending on what problem was solved.

This year there will be $k$ problems. Thus $k$ employees will be needed to inflate balloons. Each employee will inflate one balloon for each team that solves their problem.

Hannes was one of the people hired to inflate balloons this year and had to work hard since so many people solved his problem. He found this unfair since he was paid the same amount as everyone else.

After the contest Hannes thinks:

What problem could I have been assigned in order to do the least work?

Could you answer this question for Hannes?

Input

The first line of the input contains two integers $1\le k,q\le {10}^5$, where $k$ denotes the number of problems and $q$ denotes how many problems were solved in total. Next there are $q$ lines, each containing two integers $1\le a_i\le {10}^5,1\le b_i\le k$ which means that team $a_i$ solved problem $b_i$. No team solves the same problem more than once.

Output

Print a single integer, the minimum number of balloons Hannes could have had to inflate.

Scoring

2 3
1 1
2 1
3 2

1

3 5
1 1
2 1
3 1
4 1
5 2

0