问题描述

yk对每支球队定义了一个支持程度$M$，yk最多只会愿意不看 $M[i]$ 场第 $i$ 支球队的现场比赛，可惜世界杯门票是很贵滴，yk希望你能告诉他买门票的费用最少是多少（yk的数学不好，只能请你帮忙啦~）。

• 注:赛制为淘汰赛，球队从 $0$ 开始编号，每一轮编号为$2k$ 的队伍和编号为 $2k+1$ 的队伍进行一次比赛，输的队伍出局，赢的队伍进入下一轮，在下一轮中的编号为 $k$ ，并假定所有比赛时间没有重叠（如果yk不是囊中羞涩的话，他可以看完所有的比赛）。下图是一张赛程表，圆圈中的数字表示这一场比赛的门票费。

简要题意： By Nantf

给定一棵深度为 $P$ 的二叉树，将叶子标号为 $0$ 到 $2^{P-1}-1$。

现在要选出一些点，使得对于每个叶子 $i$，从叶子 $i$ 到根的路径上至多有 $\min(M_{2i},M_{2i+1})$ 个点可以不选。

问选出点的权值和的最小值。

输入格式

第$1$行$1$个整数$T$，表示数据的组数。以下$T$组数据。对每一组数据：

第$1$行$1$个整数$P$，表示比赛一共会进行$P$轮（即参赛队伍有$2^P$支）

第$2$行，$2^P$个整数，第$i$个整数表示$M[i]$

第$i+2$行，$2^{P-i}$个整数，表示第 $i$ 轮中每一场比赛的门票费用$1 \leq i \leq P$

输出格式

$T$行输出$T$组数据的答案。

对每一组数据输出$1$行Case #x: y

其中$x、y$为正整数表示第$x$组数据中买门票的最少费用是$y$

样例

样例输入

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

样例输出

Case #1: 2
Case #2: 1350

样例解释

对于第$2$组样例，赛程表为题目中给出的图。因为$M[5]=0$，所以yk必须买下第$5$支球队可能参加的所有比赛的门票，共计$1250$元。再买一张球队 $0$ 和球队 $1$ 比赛的门票即可满足所有要求，一共用去$1350$元。

数据范围与提示

• $1\leq T \leq 20 ；1 \leq P \leq 10$
• 门票价格不超过100000；
• 对40%的数据，每一场比赛的门票价格都为 $1$.
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$262144\mathrm{KB}$