풍선

풍선

Forritunarkeppni Framhaldsskólanna에서는 모든 팀이 해결한 문제마다 풍선을 하나씩 받으며, 해결한 문제에 따라 풍선의 색이 다르다.

올해는 $k$개의 문제가 출제된다. 따라서 풍선을 불 직원 $k$명을 고용해야 한다. 각 직원은 자신이 담당한 문제를 해결한 각 팀에 줄 풍선을 하나씩 분다.

Hannes는 올해 풍선을 불도록 고용된 사람 중 하나였으며, 자신의 문제를 해결한 팀이 매우 많아서 아주 많은 풍선을 불어야 했다. 그는 다른 모든 직원과 같은 임금을 받았으므로 이를 불공평하다고 생각한다.

대회가 끝난 뒤 Hannes는 다음과 같은 의문을 품었다.

어떤 문제를 맡았더라면 풍선을 가장 적게 불 수 있었을까?

Hannes를 위해 이 질문에 답할 수 있는가?

점수

그룹 | 점수 | 제한

1 | 50 | $1 \le k,q,a_i \le 100$

2 | 50 | 추가 제한 없음

첫째 줄에 두 정수 $1 \le k,q \le 10^5$가 주어진다. 여기서 $k$는 문제 수를 나타내고, $q$는 해결된 문제의 총수를 나타낸다. 이어서 $q$개의 줄이 주어지며, 각 줄에는 두 정수 $1 \le a_i \le 10^5, 1 \le b_i \le k$가 주어진다. 이는 $a_i$번 팀이 $b_i$번 문제를 해결했다는 뜻이다. 어떤 팀도 같은 문제를 두 번 이상 해결하지 않는다.

Hannes가 불어야 했을 풍선 수의 최솟값을 나타내는 정수 하나를 출력한다.