你是 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$ 是公司开始重组时的美元金额 ($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$。

最后一个测试用例后跟一行包含三个零。

输出格式

对于每个测试用例，显示其用例编号，后跟 ACM 在第 $D+1$ 天结束时可以拥有的最大美元金额。

请遵循样例输出的格式。

样例

样例输入 1

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

样例输出 1

Case 1: 44