iktk   1년 전

문제

안톤은 매일 아침 버스를 타고 출근한다.

버스 는 $1$번 정류장부터 $n$번 정류장까지 총 $n$개의 정류장으로 이루어진 경로를 운행한다. 버스는 각 정류장에서 다음 정류장까지 이동하는데 1분이 걸리고 승객이 타고 내리는 시간은 무시한다. 안톤은 첫 번째 정류장에서 타고 마지막 정류장에서 내린다.

버스에는 $m$개의 좌석이 일렬로 배열되어 있으며 입구에서 가장 가까운 좌석이 $1$번이고 가장 먼 좌석이 $m$번이다. 각 좌석에는 한 명의 승객이 앉을 수 있고, 각 좌석 옆에 한 명의 승객이 서 있을 수 있다.

승객이 버스에 타면 입구에서 가장 가까운 빈 좌석에 앉습니다. 만약 빈 좌석이 없다면, 옆에 승객이 서 있지 않은 입구에서 가장 가까운 자리를 찾아 그 옆에 선다. 만약 그런 좌석도 없다면 그는 버스에 타지 않는다.

좌석에 앉은 승객은 자신의 목적지에 도착하면 내린다. 서 있는 승객은 빈 자리가 나더라도 앉지 않고 그대로 서 있다.

각 정류장에 도착하면, 먼저 그 정류장이 목적지인 승객들이 모두 내린 후에 그 정류장에서 출발하는 승객들이 버스에 탑승합니다.

안톤은 1번 정류장에서 버스를 타서 $m$개의 좌석 중 하나에 앉으려고 한다. 안톤은 버스에 탈 승객들이 어디서 타서 어디서 내리는지 모두 알고 있으며, 자신이 앉아 있는 좌석 옆에 승객이 서 있는 것을 싫어한다. 안톤은 자신이 앉은 좌석 옆에 승객이 서 있는 시간을 최소화하고 싶다.

입력

입력 데이터의 첫 번째 라인에는 3개의 정수 $n$, $m$ 그리고 $k$ ---정류장 수, 버스의 좌석 수, 안톤 이외의 승객 수($2 \le n \le 10^9$, $1 \le m \le 2\cdot10^5$, $0 \le k \le 2\cdot10^5$) 가 주어진다.

다음 $k$ 줄은 2개의 정수 $a_i$, $b_i$가 주어진다.

$i$번 승객이 $a_i$번 정류장에서 타고 $b_i$번 정류장에서 내린다는 뜻이다. ($1 \le a_i < b_i \le n$)

한 명 이상의 사람이 같은 정류장에서 버스에 탑승하는 경우 입력에 나열된 순서대로 버스에 탑승한다.

출력

같은 줄에 두 개의 숫자를 출력하라--- 안톤이 앉은 좌석 옆에 승객이 서 있는 최소 총 시간(분)과 이를 위해 앉아야 하는 장소의 번호.

그런 곳이 여러 곳 있다면 입구에서 가장 가까운 좌석 번호를 출력한다.

댓글을 작성하려면 로그인해야 합니다.