四年一度的世界杯又到了，Varva 正在前往南非的路上，正好赶上锦标赛的第二阶段。

在第二阶段（也称为淘汰赛阶段），每场比赛总会产生一名胜者；获胜的队伍晋级下一轮，而失败的队伍则被淘汰出局。该阶段共有 $2^P$ 支队伍参赛，编号从 $0$ 到 $2^P - 1$。淘汰赛阶段共包含 $P$ 轮。在每一轮中，每支剩余的队伍都要进行且仅进行一场比赛。具体的配对方式和比赛顺序是通过依次选择编号最小的两支剩余队伍进行配对来确定的。当一轮中的所有比赛结束后，下一轮随即开始。

为了帮助他决定观看哪些比赛，Varva 根据他对特定队伍的喜爱程度整理了一份限制清单。具体来说，对于每支队伍 $i$，他最多愿意错过该队在锦标赛中参加的 $M[i]$ 场比赛。

Varva 需要购买一套门票，以确保无论比赛结果如何，他的偏好都能得到满足。除此之外，他希望花费尽可能少的钱。你的目标是找出他购买门票所需的最少金额。

比赛门票需要提前（锦标赛开始前）购买，且每场比赛的票价已知。注意，在小数据集中，所有比赛的票价相同；而在大数据集中，票价可能不同。

上图展示了一个示例锦标赛赛程及票价。假设限制条件由数组 $M = \{1, 2, 3, 2, 1, 0, 1, 3\}$ 给出，最优策略如下：由于我们不能错过队伍 5 的任何一场比赛，我们需要花费 50、400 和 800 来购买队伍 5 可能参加的所有比赛的门票。此时，除了队伍 0 之外，其他队伍的限制条件也已满足。解决此问题的最佳方案是购买队伍 0 第一轮比赛的门票，额外花费 100，总计 1350。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个用例的第一行包含一个整数 $P$。下一行包含 $2^P$ 个整数，即限制条件 $M[0], \dots, M[2^P-1]$。

接下来的 $P$ 行包含所有比赛的票价：该块的第一行包含 $2^{P-1}$ 个整数，表示第一轮比赛的票价；第二行包含 $2^{P-2}$ 个整数，表示第二轮比赛的票价，以此类推。最后一行包含一个整数，表示世界杯决赛的票价。票价按比赛进行的顺序排列。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是 Varva 购买门票所需的最少金额。

样例

输入格式 1

2
2
1 1 0 1
1 1
1
3
1 2 3 2 1 0 1 3
100 150 50 90
500 400
800

输出格式 1

Case #1: 2
Case #2: 1350