Machine Works

You are the director of Arbitrarily Complex Machines (ACM for short), a company that produces advanced machinery using even more advanced machinery. The old production machinery has broken down, so you need to buy new production machines. Your goal is to make as much money as possible during the restructuring period. During this period you can buy and sell machines and operate them for profit while ACM owns them. Because of space restrictions, ACM can own at most one machine at a time.

During the restructuring period there will be several machines for sale. Being an expert in the advanced-machine market, you already know the price $P_i$ and the availability day $D_i$ of each machine $M_i$. Note that if you do not buy machine $M_i$ on day $D_i$, then someone else will, and it will not be available later. You cannot buy a machine if ACM has less money than its price.

If you buy machine $M_i$ on day $D_i$, then ACM can operate it starting on day $D_i + 1$. Each day the machine operates, it produces a profit of $G_i$ dollars.

You may sell a machine to reclaim part of its purchase price on any day after you bought it. Each machine has a resale price $R_i$ for which it may be sold back to the market. You cannot operate a machine on the day you sell it, but you may sell a machine and use the proceeds to buy a new machine on the same day.

Once the restructuring period ends, ACM sells any machine it still owns. Your task is to maximize the amount of money ACM makes during the restructuring.

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 \le 10^5$), $C$ is the number of dollars ACM starts with ($C \le 10^9$), and $D$ is the number of days the restructuring lasts ($D \le 10^9$).

Each of the next $N$ lines describes one machine for sale with four integers $D_i$, $P_i$, $R_i$, and $G_i$: the day the machine is for sale, the price to buy it, the price for which it may be resold, and the daily profit from operating it. These satisfy $1 \le D_i \le D$, $1 \le R_i < P_i \le 10^9$, and $1 \le G_i \le 10^9$.

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

For each test case, display its case number followed by the largest number of dollars ACM can have at the end of day $D + 1$. Print it in the form Case X: Y, where $X$ is the test case number (starting from 1) and $Y$ is that largest number of dollars.