SP15061 GCJ102B - World Cup 2010

四年后，又是世界杯了，瓦尔瓦正在前往南非的路上，正好赶上了世界杯的第二阶段。 在第二阶段(也称为淘汰赛阶段)，每场比赛总是有一名胜利者；获胜的球队进入下一轮，而输队则被淘汰出局。有两个P在这个阶段比赛的队伍，用0到2的整数来标识。P-1.击倒阶段由P轮组成。在每轮比赛中，剩下的每支球队都要打一场比赛。准确的配对和匹配顺序是通过依次选择两个标识符最低的剩余球队并在一场比赛中配对来确定的。在一轮比赛结束后，下一轮就开始了。 为了帮助他决定看哪一场比赛，瓦尔瓦根据他对某支球队的喜爱程度，编制了一份约束列表。具体而言，每个团队i他是最多愿意错过 M[i]与球队在比赛中的比赛相匹配。 瓦尔瓦需要买一套票，以保证他的偏好得到满足，不管比赛结果如何。除此之外，他只是想花尽可能少的钱。你的目标是找到最低金额他需要花在票上。 比赛的门票需要预先购买(在比赛开始之前)，每场比赛的门票价格都是已知的。注意，在小输入中，所有匹配的票价都是相等的，而在大输入中，它们可能是不同的。 ## 例： 比赛时间表样本和门票价格如上图所示。假设约束由数组提供M = {1, 2, 3, 2, 1, 0, 1, 3}最优策略如下：由于我们不能错过5队的任何比赛，我们需要花费50，400和800购买所有5队可能参加的比赛的门票。现在，其他球队的约束也被这些票所满足，除了第0组。解决这一问题的最佳选择是购买0队第一轮比赛的门票，再花费100英镑，使总数达到1350张。

输入的第一行给出了测试用例的数量，T. T接下来是测试用例。每一种情况都从包含一个整数的一行开始。P..下一行包含2^{P} P 整数-约束M[0], ..., M[2 P ^{P} P -1]. 以下块P行包含所有匹配的票价：块的第一行包含2。^{P1} P−1 整数-第一轮比赛的门票价格，第二行包含2^{P2} P−2 整数-第二轮比赛的门票价格等P在世界杯的最后一场比赛中，线包含一个整数票的价格.价格是按比赛的顺序列出的。

对于每个测试用例，输出一行包含“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 ```