세탁물 묶음 나누기

문제

세탁소의 컨베이어에 N벌의 세탁물이 1번부터 N번까지 순서대로 놓여 있다. i번 세탁물의 무게는 w_i이고, 세탁하는 데 필요한 시간은 t_i분이다. 세탁물의 순서는 바꿀 수 없으며, 연속한 세탁물을 한 묶음으로 만들어 세탁기에 넣어야 한다. 모든 세탁물은 정확히 하나의 묶음에 속해야 하고, 묶음들은 번호 순서대로 하나씩 세탁기를 사용한다. 한 묶음에 들어간 세탁물의 무게 합은 세탁기 용량 C 이하여야 한다. 묶음 하나를 세탁하는 데는 준비 시간으로 F분이 들고, 묶음 안의 세탁물이 동시에 돌아가므로 그 묶음에서 가장 오래 걸리는 세탁물의 시간만큼 더 걸린다. 즉 한 묶음의 소요 시간은 F + (묶음에 속한 t 값의 최댓값)이다. 모든 묶음의 소요 시간을 합한 전체 시간이 최소가 되도록 묶음을 나눌 때, 그 최소 전체 시간을 구하라. 무게가 C보다 큰 세탁물이 하나라도 있으면 어떤 묶음에도 넣을 수 없으므로 이 경우에는 -1을 출력한다. 묶음의 개수에는 제한이 없고, 묶음은 최소 한 벌의 세탁물을 포함해야 한다. 입력은 모두 정수이며 답도 정수이다.

입력

첫 줄에 N, C, F가 공백으로 구분되어 주어진다. 이어지는 N개의 줄에 i번 세탁물의 무게 w_i와 시간 t_i가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ C ≤ 10^14, 0 ≤ F ≤ 10^9, 1 ≤ w_i ≤ 10^9, 1 ≤ t_i ≤ 10^9 이다.

출력

최소 전체 시간을 한 줄에 출력한다. 불가능하면 -1을 출력한다.

4 10 2
4 3
5 7
3 2
6 5

16

2 5 1
6 1
2 2

-1

1 7 0
7 9

9

출처: Devin.KR 자체 제작