沙姆沙伊赫市计划在市内开设一项共享单车服务。他们将在市内的战略要点建立 $N$ 个自行车站点。每个站点将拥有容量 $C$，这意味着在早晨最多有 $C$ 名通勤者可以从一个站点取走自行车，而在晚上最多有 $C$ 名通勤者可以将自行车归还到一个站点。这些数字是独立的（即，即使早晨没有从某个站点取走自行车，该站点在晚上仍然可以接收 $C$ 辆自行车）。

你身处该服务的规划部门，并决定进行一些市场调研以确保服务能够盈利。你发现：共有 $M$ 个不同的潜在通勤者群体想要使用你的服务。每个群体由 $P$ 个人组成，同一群体中的每个人都希望以相同的方式使用服务：他们都想在早晨从某个起始站点 $St$ 取走一辆自行车，并在晚上将其归还到某个（可能是同一个）终点站点 $En$，且每个人愿意为此服务支付恰好 $X$ 的费用。由于通勤者需要整天使用自行车，因此一辆自行车不能被多名通勤者使用。

站点的自行车数量可能无法满足所有通勤者。在这种情况下，你可以自由选择能够满足的通勤者子集，以使总支付金额最大（你不需要选择整个群体，选择同一群体中的一个子集也是可以的）。

现在，掌握了上述信息后，你必须选择一个最佳的容量 $C$（可以是零）。当然，拥有更大的容量需要付出成本。容量为 $C$ 的成本是 $D \times C$。你能算出该服务所能产生的最大利润（总收入 - 总成本）吗？

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 50$)，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含 3 个由空格分隔的整数 $N$、$M$ 和 $D$ ($1 \le N \le 50$, $1 \le M \le 250$, $1 \le D \le 100,000$)，分别表示站点数量、潜在通勤者群体数量以及所有站点中每增加一个单位容量的成本。接下来的 $M$ 行，每行包含 4 个整数 $P$、$St$、$En$ 和 $X$ ($1 \le P \le 100,000$, $1 \le St, En \le N$, $1 \le X \le 100,000$)，分别表示该群体的人数、通勤的起点和终点，以及每个人愿意支付的金额。

输出格式

对于每个测试用例，打印一行包含 “Case n:”（不含引号），其中 $n$ 是测试用例编号（从 1 开始），后跟一个空格，再跟上最大利润。

样例

输入 1

2
2 3 3
10 1 2 2
10 1 1 2
10 2 2 2
2 3 5
10 1 2 10
10 1 1 2
10 2 2 2

输出 1

Case 1: 10
Case 2: 50