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

给你一个整数数组 price 表示物品价格，其中 price_i 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs_i 是需要购买第 i 件物品的数量。

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

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

第一行输入 n + 1 个整数，前 n 个数为 price 数组，最后一个整数为大礼包的数量（special 数组的长度）m。

接下来 2 到 m + 1 行每行 n + 1 个整数，第 i 行表示 special_{i - 1}。

最后一行输入 n 个整数表示 need 数组。

题目保证 1 \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。

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

样例一解释：

1. 第一行 2 5 2：前两个是 price 数组的值 最后一个是 special 数组的长度 m，即 2 代表下面的两行都是 special 数组的值；
2. 第二行 3 0 5：代表 special_0 的值。
3. 第三行 1 2 10：代表 special_1 的值。
4. 第四行 3 2：need 数组的值。

答案解释：有 A 和 B 两种物品，价格分别为 2 和 5。大礼包 1，你可以以 5 的价格购买 3 个 A 和 0 个 B；大礼包 2，你可以以 10 的价格购买 1 个 A 和 2 个 B 。

需要购买 3 个 A 和 2 个 B，所以付 10 购买大礼包 2，以及 4 用于另外购买 2 个 A。