회의실 희망 시간 집계

문제

공유 사무실에서 회의실 한 곳의 이용 수요를 조사하고 있다. 조사 대상인 하루를 같은 길이의 시간 칸 N개로 나누고, 이른 시간부터 1번부터 N번까지 번호를 붙였다. 각 팀은 회의를 진행하고 싶은 시간 구간을 하나 제출한다. 제출한 구간은 시작 시간 칸 L과 마지막 시간 칸 R로 표현하며, L번 칸과 R번 칸을 모두 포함한다. 이번 조사는 실제 예약을 확정하는 절차가 아니다. 따라서 서로 다른 팀이 같은 시간 칸을 희망해도 모든 신청을 그대로 접수한다. 담당자는 각 시간 칸을 희망하는 신청이 몇 개인지 세어, 수요가 가장 많이 몰리는 시간 칸을 찾으려 한다. 어떤 신청의 구간에 들어 있는 시간 칸은 그 신청으로 수요가 각각 1씩 증가한다. 신청 하나가 여러 시간 칸에 걸쳐 있어도, 특정 시간 칸의 수요에는 최대 1만 더한다. 예를 들어 2번 칸부터 4번 칸까지의 신청은 2번, 3번, 4번 칸의 수요를 각각 1씩 증가시키고 다른 칸에는 영향을 주지 않는다. 시작과 마지막 번호가 같으면 그 시간 칸 하나만 희망한다는 뜻이다. 서로 같은 구간을 제출한 신청이 여러 개 있을 수 있다. 이들은 각각 별개의 신청이므로 모두 센다. 또한 한 신청의 마지막 칸과 다른 신청의 시작 칸이 같다면, 해당 시간 칸에는 두 신청이 모두 포함된다. 시간 칸 번호 사이에 별도의 빈 시간이나 준비 시간은 두지 않는다. 모든 신청을 집계한 뒤 가장 큰 수요와 그 수요를 갖는 시간 칸 하나를 구한다. 가장 큰 수요를 갖는 칸이 여러 개라면 번호가 가장 작은 칸을 선택한다. 단, 제출된 신청이 하나도 없으면 선택할 시간 칸이 없는 것으로 정하고, 가장 큰 수요와 시간 칸 번호를 모두 0으로 출력한다.

입력

첫째 줄에 정수 N과 M이 공백으로 주어진다. 다음 M개 줄에는 각 신청의 시작 시간 칸 L과 마지막 시간 칸 R이 공백으로 주어진다.
1 ≤ N ≤ 40,000
0 ≤ M ≤ 25,000
1 ≤ L ≤ R ≤ N
모든 수는 정수다.

출력

가장 큰 수요와 선택한 시간 칸 번호를 공백으로 구분하여 한 줄에 출력한다. M이 0이면 0 0을 출력한다.

8 4
2 5
4 7
4 4
6 8

3 4

7 3
1 2
5 6
5 6

2 5

3 0

0 0

출처: Devin.KR 자체 제작