묶음 배달 비용

문제

택배 기사 한 명이 물류 창고에서 출발해 일직선 도로를 따라 물건을 배달한다. 창고는 도로의 0 지점에 있고, 오늘 배달할 물건은 1번부터 N번까지 번호 순서대로 쌓여 있어 반드시 이 순서를 지켜 실어야 한다. i번 물건의 무게는 w_i이고, 도착지는 창고에서 d_i만큼 떨어진 지점이다. 기사는 여러 번에 나누어 출발한다. 한 번 출발할 때는 번호가 연속인 물건들을 한 묶음으로 싣고, 묶음에 실린 물건의 무게 합은 적재 한도 C 이하여야 한다. 묶음을 싣고 출발하면 묶음 안에서 가장 먼 도착지까지 갔다가 창고로 돌아온다. 가는 길에 지나는 도착지의 물건은 모두 배달할 수 있다. 이 한 번의 운행에 드는 비용은 (묶음 안에서 가장 먼 도착지의 거리 × 2 + S)이다. S는 출발할 때마다 드는 고정 비용이다. 묶음의 개수에는 제한이 없지만, 묶음들은 서로 겹치지 않고 1번부터 N번까지를 빠짐없이 나누어 담아야 한다. 모든 물건을 배달하는 데 드는 비용의 합이 최소가 되도록 묶었을 때, 그 최솟값을 구하시오. 물건 하나의 무게는 항상 C 이하이므로 답은 반드시 존재한다.

입력

첫 줄에 정수 N, C, S가 공백으로 구분되어 주어진다. 다음 N개의 줄에 i번 물건의 무게 w_i와 거리 d_i가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ C ≤ 10^9, 0 ≤ S ≤ 10^9, 1 ≤ w_i ≤ C, 1 ≤ d_i ≤ 10^9이다. 모든 값은 정수이다.

출력

모든 물건을 배달하는 데 드는 최소 총비용을 정수 하나로 출력한다.

5 10 1
4 5
5 2
3 7
6 1
4 4

35

1 5 2
5 3

8

3 3 0
2 1
2 1
2 1

6

출처: Devin.KR 자체 제작