레이팅 미적용당신은 더욱 진보한 기계를 사용해 첨단 기계를 생산하는 회사 Arbitrarily Complex Machines(줄여서 ACM)의 이사이다. 기존 생산 기계가 고장 나서 회사를 위해 새 생산 기계를 사야 한다. 목표는 구조조정 기간 동안 최대한 많은 돈을 버는 것이다. 이 기간 동안 기계를 사고팔 수 있으며, ACM이 소유한 동안 기계를 가동해 이익을 낼 수 있다. 공간 제약 때문에 ACM은 한 번에 최대 한 대의 기계만 소유할 수 있다. 구조조정 기간 동안 여러 기계가 판매될 것이다. 첨단 기계 시장의 전문가인 당신은 각 기계 \(Mi\)의 가격 \(Pi\)와 판매되는 날 \(Di\)를 이미 알고 있다. 기계 \(Mi\)를 \(Di\)일에 사지 않으면 다른 누군가가 사 버려서 이후에는 살 수 없다는 점에 유의하라. 말할 것도 없이, ACM이 가진 돈이 기계 가격보다 적으면 그 기계를 살 수 없다. 기계 \(Mi\)를 \(Di\)일에 사면 ACM은 \(Di + 1\)일부터 그 기계를 가동할 수 있다. 기계가 가동되는 날마다 회사에 \(Gi\)달러의 이익이 발생한다. 기계를 산 뒤에는 어느 날이든 팔아서 구매 가격의 일부를 회수할 수 있다. 각 기계에는 시장에 되팔 수 있는 재판매 가격 \(Ri\)가 있다. 기계를 파는 날에는 그 기계를 가동할 수 없지만, 같은 날 기계를 팔아 그 돈으로 새 기계를 살 수는 있다. 구조조정 기간이 끝나면 ACM은 아직 소유한 기계를 모두 판다. 당신의 임무는 구조조정 동안 ACM이 버는 돈을 최대화하는 것이다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 세 양의 정수 \(N\), \(C\), \(D\)가 있는 줄로 시작한다. \(N\)은 판매되는 기계의 수(\(N \le 10^{5}\)), \(C\)는 구조조정 시작 시 회사가 가진 달러 수(\(C \le 10^{9}\)), \(D\)는 구조조정이 지속되는 일수(\(D \le 10^{9}\))이다. 다음 \(N\)개의 줄은 각각 판매되는 기계 한 대를 설명한다. 각 줄에는 네 정수 \(D_{i}\), \(P_{i}\), \(R_{i}\), \(G_{i}\)가 주어지며, 각각 기계가 판매되는 날, 살 수 있는 달러 가격, 되팔 수 있는 달러 가격, 기계를 가동해 얻는 일일 이익을 나타낸다. 이 수들은 \(1 \le Di \le D\), \(1 \le Ri < Pi \le 10^{9}\), \(1 \le Gi \le 10^{9}\)를 만족한다. 마지막 테스트 케이스 다음에는 0 세 개가 있는 줄이 주어진다.
각 테스트 케이스마다 케이스 번호와 함께 \(D + 1\)일이 끝났을 때 ACM이 가질 수 있는 최대 달러 수를 출력한다. 샘플 출력의 형식을 따른다.
6 10 20
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1
0 0 0
ICPC 2011 World Finals Problem F: Machine Works
Case 1: 44