기계 공작소

당신은 더 발전된 기계를 이용해 발전된 기계를 만드는 회사 Arbitrarily Complex Machines(줄여서 ACM)의 이사이다. 기존 생산 기계가 고장 나서 새 생산 기계를 사야 한다. 목표는 구조 조정 기간 동안 최대한 많은 돈을 버는 것이다. 이 기간 동안 당신은 기계를 사고팔 수 있으며, ACM이 소유하고 있는 동안 기계를 가동해 이익을 낼 수 있다. 공간 제약 때문에 ACM은 한 번에 최대 한 대의 기계만 소유할 수 있다.

구조 조정 기간에는 여러 대의 기계가 판매된다. 당신은 이 시장의 전문가라서 각 기계 $M_i$의 가격 $P_i$와 판매되는 날 $D_i$를 이미 알고 있다. 만약 $D_i$일에 기계 $M_i$를 사지 않으면 다른 사람이 사 가서 나중에는 살 수 없다. 또한 ACM이 가진 돈이 기계의 가격보다 적으면 그 기계를 살 수 없다.

$D_i$일에 기계 $M_i$를 사면, ACM은 $D_i + 1$일부터 그 기계를 가동할 수 있다. 기계가 가동하는 날마다 $G_i$달러의 이익이 발생한다.

기계를 산 뒤에는 아무 날에나 팔아 구매 가격의 일부를 회수할 수 있다. 각 기계에는 되팔 수 있는 가격 $R_i$가 있다. 기계를 파는 날에는 그 기계를 가동할 수 없지만, 같은 날에 기계를 팔고 그 돈으로 새 기계를 살 수는 있다.

구조 조정 기간이 끝나면 ACM은 소유하고 있는 기계를 모두 판다. 당신의 과제는 구조 조정 기간 동안 ACM이 버는 돈을 최대로 만드는 것이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 세 양의 정수 $N$, $C$, $D$가 주어진다. $N$은 판매되는 기계의 수($N \le 10^5$), $C$는 ACM이 처음 가진 달러의 수($C \le 10^9$), $D$는 구조 조정이 지속되는 날 수($D \le 10^9$)이다.

다음 $N$개의 줄에는 각각 판매되는 기계 하나를 나타내는 네 정수 $D_i$, $P_i$, $R_i$, $G_i$가 주어진다. 각각 기계가 판매되는 날, 사는 가격, 되파는 가격, 가동으로 얻는 하루 이익이다. 이들은 $1 \le D_i \le D$, $1 \le R_i < P_i \le 10^9$, $1 \le G_i \le 10^9$을 만족한다.

마지막 테스트 케이스 다음 줄에는 세 개의 $0$이 주어진다.

각 테스트 케이스마다 케이스 번호와, $D + 1$일이 끝났을 때 ACM이 가질 수 있는 최대 달러 수를 Case X: Y 형식으로 출력한다. 여기서 $X$는 케이스 번호(1부터 시작)이고 $Y$는 그 최대 달러 수이다.