Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem D: Machines

Problem D: Machines

Time Limit: 5 Sec  Memory Limit: 256 MB
Submit: 4  Solved: 2
[Submit][Status][Web Board]

Description

Recently Lint want to buy some machines. His goal is to make as much money as possible in some days. During this period you will be able to buy and sell machines and operate them for profit while Lint owns them. Due to space restrictions, Lint can own at most one machine at a time.

There will be several machines for sale. Lint already knows the price Pi and the availability day Di for each machines Mi. Note that if he does not buy machine Mi on day Di, then somebody else will buy it and it will not be available later. Needless to say, Lint cannot buy a machine if he has less money than the price of the machine.

If Lint buy a machine Mi on day Di, then he can operate it starting on day Di + 1. Each day that the machine operates, it produces a profit of Gi dollars.

Lint may decide to sell a machine to reclaim a part of its purchase price any day after he’ve bought it. Each machine has a resale price Ri for which it may be resold to the market. He cannot operate a machine on the day that you sell it, but he may sell a machine and use the proceeds to buy a new machine on the same day.

Once the period ends, Lint will sell any machine that it still owns. Can you help Lint to maximize the amount of money that he makes during these days.

Input

The input consists of several test cases. Each test case starts with a line containing three positive integers N, C, and D. N is the number of machines for sale (N <= 10^5), C is the number of dollars with which the Lint has (C <= 10^9), and D is the number of days (D <= 10^9).

Each of the next N lines describes a single machine for sale. Each line contains four integers Di, Pi, Ri and Gi,
denoting (respectively) the day on which the machine is for sale, the dollar price for which it may be bought, the
dollar price for which it may be resold and the daily profit generated by operating the machine. These numbers satisfy
1 <= Di <= D, 1 <= Ri < Pi <=10^9 and 1 <= Gi <= 10^9.

The last test case is followed by a line containing three zeros.

Output

For each test case, display its case number followed by the largest number of dollars that Lint can have at the end of day D + 1.
Follow the format of the sample output.

Sample Input

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

Sample Output

Case 1: 44

HINT

[Submit][Status][Web Board]