페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8032
서브태스크

머신(Machine) 1s 1024MB

문제

당신은 Arbitrarily Complex Machines (약칭 ACM)라는 회사의 이사입니다. 이 회사는 고급 기계를 사용하여 더 고급 기계를 생산합니다. 기존 생산 기계가 고장 나서 새로운 생산 기계를 구입해야 합니다. 목표는 구조조정 기간 동안 가능한 한 많은 돈을 버는 것입니다. 이 기간 동안 기계를 사고팔고, ACM이 소유하고 있는 동안 운영하여 이익을 얻을 수 있습니다. 공간 제약으로 인해 ACM은 한 번에 최대 한 대의 기계만 소유할 수 있습니다.

구조조정 기간 동안 여러 대의 기계가 판매될 것입니다. 고급 기계 시장의 전문가로서 각 기계 M_i의 가격 P_i와 구매 가능일 D_i를 미리 알고 있습니다. D_i일에 기계 M_i를 사지 않으면 다른 사람이 사버려 나중에는 구할 수 없습니다. 물론 ACM의 돈이 기계의 가격보다 적으면 기계를 살 수 없습니다.

기계 M_i를 D_i일에 구입하면 ACM은 D_i + 1일부터 기계를 운영할 수 있습니다. 기계를 운영하는 매일은 회사에 G_i 달러의 이익을 가져옵니다.

기계를 구입한 후 언제든지 판매하여 구매 가격의 일부를 회수할 수 있습니다. 각 기계는 시장에 되팔 수 있는 리셀 가격 R_i를 가지고 있습니다. 기계를 판매하는 날에는 기계를 운영할 수 없지만, 같은 날 기계를 팔고 그 수익으로 새 기계를 구입할 수 있습니다.

구조조정 기간이 끝나면 ACM은 소유 중인 모든 기계를 판매합니다. 구조조정 기간 동안 ACM이 벌 수 있는 돈을 최대화하는 것이 목표입니다.


입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 세 개의 양의 정수 N, C, D로 시작한다.

N은 살 수 있는 기계의 수를 나타낸다 (N ≤ 10^5)

C는 회사가 구조조정을 시작할 때 가지고 있는 달러 수를 나타낸다 (C ≤ 10^9).

D는 구조조정 기간의 일수를 나타낸다 (D ≤ 10^9).

다음 N줄 각각은 판매되는 단일 기계를 설명한다.

각 줄에는 기계가 판매되는 날짜 D_i, 구매 가격 P_i, 리셀 가격 R_i 및 기계를 운영하여 발생하는 일일 이익 G_i를 나타내는 네 개의 정수 D_i, P_i, R_i, G_i이 주어진다.

이 숫자들은 1 ≤ D_i ≤ D, 1 ≤ R_i < P_i ≤ 10^9, 1 ≤ G_i ≤ 10^9를 만족합니다.

마지막 테스트 케이스 뒤에는 세 개의 0이 포함된 줄이 있습니다.


출력

각 테스트 케이스에 대해, 케이스 번호와 D + 1일의 마지막에 ACM이 가질 수 있는 최대 달러 수를 출력합니다.

샘플 출력의 형식을 따르세요.


부분문제

번호 점수 조건
#120점

N \le 20

#230점

N \le 1000

#350점

추가 제약 조건 없음


예제 

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
Case 1: 44

출처

ICPC World Finals 2011 F번

로그인해야 코드를 작성할 수 있어요.