1633. [算法课分支限界法]大礼包

在商店中, 有 nn 件在售的物品。每件物品都有对应的价格。然而,也有一些大礼包,每个大礼包以优惠的价格捆绑销售一组物品。

给你一个整数数组 priceprice 表示物品价格,其中 priceiprice_i 是第 ii 件物品的价格。另有一个整数数组 needsneeds 表示购物清单,其中 needsineeds_i 是需要购买第 ii 件物品的数量。

还有一个数组 specialspecial 表示大礼包,长度为 mmspeciali(1im)special_i(1 \le i \le m) 也为数组,长度为 n+1n + 1 ,其中 speciali,j(0j<n)special_{i, j}(0 \le j < n) 表示第 ii 个大礼包中内含第 jj 件物品的数量,且 speciali,nspecial_{i, n}(也就是数组中的最后一个整数)为第 ii 个大礼包的价格。

返回确切满足购物清单所需花费的最低价格,你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品,即使那样会降低整体价格。任意大礼包可无限次购买。

输入

第一行输入 n+1n + 1 个整数,前 nn 个数为 priceprice 数组,最后一个整数为大礼包的数量(specialspecial 数组的长度)mm

接下来 22m+1m + 1 行每行 n+1n + 1 个整数,第 ii 行表示 speciali1special_{i - 1}

最后一行输入 nn 个整数表示 needneed 数组。

题目保证 1n=price.length=needs.length6,0pricei10,0needsi10,1m100,speciali.length=n+1,0speciali,j501 \le n = price.length = needs.length \le 6, 0 \le price_i \le 10, 0 \le needs_i \le 10, 1 \le m \le 100, special_i.length = n + 1, 0 \le special_{i, j} \le 50

输出

一行输出一个整数表示满足购物清单的最小费用。

样例

标准输入 复制文本
2 5 2
3 0 5
1 2 10
3 2
标准输出 复制文本
14

提示

样例一解释:

  1. 第一行 2 5 2:前两个是 priceprice 数组的值 最后一个是 specialspecial 数组的长度 mm,即 22 代表下面的两行都是 specialspecial 数组的值;
  2. 第二行 3 0 5:代表 special0special_0 的值。
  3. 第三行 1 2 10:代表 special1special_1 的值。
  4. 第四行 3 2needneed 数组的值。

答案解释:有 A 和 B 两种物品,价格分别为 2255。大礼包 1,你可以以 55 的价格购买 33 个 A 和 00 个 B;大礼包 2,你可以以 1010 的价格购买 11 个 A 和 22 个 B 。

需要购买 33 个 A 和 22 个 B,所以付 1010 购买大礼包 2,以及 4 用于另外购买 22 个 A。

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 2200
通过 1196