32634번 - 서강 피자

문제

매년 서강대학교는 학생들의 학업 능력 향상을 위해 $N$일 동안 피자를 제공한다.

서강대학교에는 학생 1ドル$부터 학생 $M$까지 총 $M$명의 학생이 있으며, 학생 $i$는 1ドル$일부터 $t_i$일 사이 적어도 $k_i$ 판의 피자를 받기를 요구한다. 학생은 하루에 최대 한 판의 피자만 받을 수 있다.

서강대학교는 매일 $X$판의 피자를 제공할 예정이며, 예산을 고려해 $X$를 최소화하려고 한다. 피자는 학교가 원하는 대로 나눠줄 수 있다고 할 때, 모든 학생의 요구를 만족할 수 있는 정수 $X$의 최솟값을 구하여라.

입력

첫 번째 줄에는 두 정수 $N$과 $M$이 주어진다. (1ドル \le N, M \le 2 \times 10^5$)

다음 $M$개의 줄에는 각 학생의 요구 사항을 나타내는 두 정수 $t_i$와 $k_i$가 주어진다. (1ドル \le t_i \le N,ドル 1ドル \le k_i \le t_i$)

출력

모든 학생의 요구를 만족할 수 있는 정수 $X$의 최솟값을 출력한다.

제한

힌트