회의실의 짧은 예약들

문제

한 공동 작업 공간은 하루 동안 회의실 하나를 B분간 운영한다. 운영 시간은 0분에 시작해서 B분에 끝나는 하나의 연속된 구간이다. 오늘 접수된 회의 신청은 N개이며, 각 신청에는 필요한 회의 시간만 적혀 있다. 신청자들은 시작 시각을 따로 지정하지 않았으므로 담당자가 채택한 회의들의 순서를 자유롭게 정할 수 있다. 각 회의는 중간에 끊지 않고 신청한 시간만큼 연속해서 진행해야 한다. 서로 다른 두 회의 사이에는 회의실을 정리하는 시간이 C분 필요하다. 따라서 회의를 두 개 이상 진행하면 시간표에서 바로 이웃한 회의 사이마다 정리 시간을 한 번씩 넣어야 한다. 첫 회의 전에는 이미 정리가 끝나 있으므로 준비 시간이 필요하지 않으며, 마지막 회의가 끝난 뒤의 정리 시간도 운영 시간에 포함하지 않는다. 회의끼리 겹치거나 정리 시간을 줄이는 것은 허용하지 않는다. C가 0이면 회의를 바로 이어서 진행할 수 있다. 담당자의 첫 번째 목표는 운영 시간 안에 진행하는 회의의 개수를 최대화하는 것이다. 같은 신청을 두 번 채택할 수는 없지만, 시간이 같은 서로 다른 신청은 각각 채택할 수 있다. 모든 신청을 받을 필요는 없다. 채택한 회의가 K개이고 K가 1 이상이면 필요한 총시간은 해당 회의 시간의 합에 C×(K−1)을 더한 값이다. 이 값이 B와 같아도 운영 시간 안에 진행할 수 있다. 두 번째 목표는 최대 개수의 회의를 진행하는 방법 중 필요한 총시간을 최소화하는 것이다. 여기서 총시간에는 회의와 회의 사이의 정리 시간만 포함하며, 임의로 비워 두는 대기 시간은 포함하지 않는다. 프로그램은 최대 회의 개수와 그 개수를 달성하는 최소 총시간을 구해야 한다. 어떤 회의도 진행할 수 없으면 두 값 모두 0이다. 같은 두 값을 만드는 신청 조합이나 진행 순서가 여러 개여도 조합과 순서는 출력하지 않는다.

입력

첫째 줄에 정수 N, B, C가 공백으로 구분되어 주어진다. 1≤N≤50,000, 1≤B≤1,000,000,000, 0≤C≤1,000이다. 둘째 줄에 각 신청의 회의 시간 A1부터 AN까지 정수 N개가 공백으로 구분되어 주어진다. 모든 i에 대해 1≤Ai≤1,000이다.

출력

진행할 수 있는 최대 회의 개수와, 그 개수의 회의를 진행하는 데 필요한 최소 총시간을 공백으로 구분하여 출력한다. 진행 가능한 회의가 없으면 0 0을 출력한다.

5 25 3
9 4 8 4 12

3 22

3 2 0
3 5 4

0 0

4 13 1
4 2 3 1

4 13

출처: Devin.KR 자체 제작