시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB33261890.000%

문제

$1$층부터 $M$층까지 $M$개 층으로 이루어진 설곽 호텔에는 $1$대의 엘리베이터가 있습니다. 어느 날 경곽 학생 $N$명이 설곽 호텔에 머무르게 되었습니다. 모든 학생은 엘리베이터를 이용해 자신의 객실이 있는 층으로 올라가야 합니다.

$i$번 학생은 시각 $t_i$초에 $1$층 로비에 도착해 줄의 맨 뒤에 섭니다. 단, 여러 학생이 동시에 도착하는 경우 번호가 작은 학생부터 순서대로 줄을 섭니다. 엘리베이터는 $1$층에 있을 때 줄의 맨 앞에서부터 최대 $C$명을 태워 운행을 시작할 수 있습니다.

엘리베이터가 운행을 시작하면 탑승자들의 객실 중 가장 높은 층인 $X$층까지 올라가며, 이 과정에서 학생들은 자신의 층에서 내립니다. 학생들이 내리면서 엘리베이터가 정지하는 시간은 무시하며, 한 층을 이동하는 데에 $1$초가 걸립니다. $1$층 로비에 아직 객실로 가지 못한 학생이 남아 있다면 엘리베이터는 $X$층에서 다시 $1$층까지 내려와야 하므로 이때 운행 시간은 $2X-2$초입니다. 모든 학생을 태운 마지막 운행이라면 그 즉시 운행이 종료하므로 이때 운행 시간은 $X-1$초입니다.

호텔 관리자인 당신은 모든 경곽 학생의 로비 도착 시각과 객실 층수를 알고 있습니다. 경곽 학생들을 줄의 앞에서부터 적당히 분할하여 엘리베이터에 탑승시켜 모든 학생이 자신의 객실 층수에 도착하는 시각을 최소화하려고 할 때, 그 최솟값을 구해봅시다.

입력

첫째 줄에 세 정수 $N$, $M$, $C$가 공백으로 구분되어 주어집니다.

둘째 줄부터 $N$개 줄에 걸쳐 각 학생의 정보 $t_{i}$, $f_{i}$가 공백으로 구분되어 주어집니다. $t_{i}$는 $i$번 학생이 $1$층 로비에 도착하는 시각, $f_{i}$는 $i$번 학생의 객실 층수입니다.

출력

첫째 줄에 모든 학생이 자신의 객실 층수에 도착하는 시각의 최솟값을 출력합니다.

제한

  • $1\le N\le 300\, 000$
  • $1\le C\le 100$
  • $C\le N$
  • $0 \le t_1\le t_2\le\dots\le t_{N}\le 10^9$
  • $2 \le M \le 10^{9}$
  • $2\le f_{i} \le M$ $(1\le i\le N)$

서브태스크

번호배점제한
17

$C = 1$

224

$1 \le i \le N$인 모든 정수 $i$에 대해 $t_{i} = 0$

333

$C \le 10$

436

추가 제한 조건이 없습니다.

예제 입력 1

5 7 1
0 3
1 2
7 5
8 2
13 6

예제 출력 1

22

예제 입력 2

5 7 2
0 3
1 2
7 5
8 2
13 6

예제 출력 2

20

채점 및 기타 정보

  • 예제는 채점하지 않는다.