你刚刚看到了一则关于一个有趣的商业计划的电视广告，该计划由 $N$ 个阶段的循环组成。 第 $i$ 个阶段有一个价值 $V_i$，它可以是正数、负数或零。当你进入第 $i$ 个阶段时，你会将 $V_i$ 加到你当前拥有的金额中，除非这会导致金额变为负数，在这种情况下，你的金额将变为 $0$。然后你进入第 $((i+1) \pmod N)$ 个阶段。

你在第 $0$ 阶段之前开始该商业计划，并拥有一定的初始金额（可能为 $0$）。你需要保证在不超过 $P$ 个阶段后拥有至少 $G$ 的金额，请问所需的最小初始金额是多少？

输入格式

输入的第一行包含测试用例的数量 $T$，随后是一个空行。 接下来是 $T$ 个测试用例；每个测试用例包含两行，随后是一个空行。第一行包含三个整数 $N$、$G$ 和 $P$，如上所述。第二行包含 $N$ 个整数；其中第 $i$ 个整数为 $V_i$，表示第 $i$ 个阶段的价值。

输出格式

对于每个测试用例，输出一行包含 “Case #x: y”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是如上所述所需的最小初始金额。

数据范围

• $1 \le T \le 100$
• $1 \le N \le 10^5$
• $1 \le G, P \le 10^{18}$
• $|V_i| \le 10^9$

样例

输入 1

3
2 10 2
3 -1
2 10 3
3 -1
1 10 10
-999

输出 1

Case #1: 7
Case #2: 5
Case #3: 10

说明

在样例 #1 中，如果你以 $7$ 的金额开始，那么经过一个阶段（第 $0$ 阶段）后，你将拥有 $10$ 的金额。这满足了在不超过 $2$ 个阶段后拥有至少 $10$ 的金额的条件。没有更小的金额可行。

在样例 #2 中，如果你以 $5$ 的金额开始，那么经过一个阶段（第 $0$ 阶段）后你将拥有 $8$ 的金额，经过两个阶段（第 $1$ 阶段）后拥有 $7$ 的金额，经过三个阶段（再次回到第 $0$ 阶段）后拥有 $10$ 的金额。没有更小的金额可行。

在样例 #3 中（顺便说一下，这是一个糟糕的商业计划！），在过程中任何时候拥有至少 $10$ 的金额的唯一方法是初始时至少拥有 $10$ 的金额，而 $10$ 是可行的最小金额。