#P18637. Knapsack Problem

Knapsack Problem

Knapsack Problem

给定 2k−12^k-1 个整数 c1,c2,…,c2k−1c_1,c_2,\ldots,c_{2^k-1} 和 kk 个整数 a0,a1,…,ak−1a_0,a_1,\ldots,a_{k-1}。

你需要选择非负整数 x1,x2,…,x2k−1x_1,x_2,\ldots,x_{2^k-1},满足对每一个 0≤j<k0\le j<k,都有

$$\sum_{i=1}^{2^k-1} \left(\left\lfloor\frac{i}{2^j}\right\rfloor\bmod2\right)x_i=a_j.$$

在满足全部条件的选择中,最大化

∑i=12k−1xici.\sum_{i=1}^{2^k-1}x_i c_i.

也就是说,类型 ii 由它的 kk 位二进制表示指定:第 jj 位为 11 时,每选一个该类型就消耗第 jj 维容量 11;第 jj 位为 00 时不消耗该维容量。每种类型都可以选择任意非负整数个,各维容量必须恰好用完。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例占三行:

  • 第一行一个整数 kk;
  • 第二行 2k−12^k-1 个整数 c1,c2,…,c2k−1c_1,c_2,\ldots,c_{2^k-1};
  • 第三行 kk 个整数 a0,a1,…,ak−1a_0,a_1,\ldots,a_{k-1}。

输出格式

对每个测试用例输出一行一个整数,表示最大价值。

数据范围

  • 1≤T≤1001\le T\le100;
  • 2≤k≤42\le k\le4;
  • 0≤ci≤1080\le c_i\le10^8;
  • 1≤aj≤1091\le a_j\le10^9。

原题没有额外的各测试用例容量总和限制。答案需要使用 64 位有符号整数。

样例输入 1

3
2
1 2 4
4 5
3
3226252 19270256 2430652 1187613 12496062 10286165 17494834
24 85 34
4
901133 6693218 13245489 14740234 16186210 11382783 19277321 3855635 16523184 10168517 16195031 971041 10303441 8395899 11618555
529321239 218214127 92942310 207467810

样例输出 1

18
1949753378
7832404777567179

样例中的每种价格序列在实际输入中占一整行;这里保留完整数据,没有省略或用于排版的反斜杠。