在商店中, 有 件在售的物品。每件物品都有对应的价格。然而,也有一些大礼包,每个大礼包以优惠的价格捆绑销售一组物品。
给你一个整数数组 表示物品价格,其中 是第 件物品的价格。另有一个整数数组 表示购物清单,其中 是需要购买第 件物品的数量。
还有一个数组 表示大礼包,长度为 。 也为数组,长度为 ,其中 表示第 个大礼包中内含第 件物品的数量,且 (也就是数组中的最后一个整数)为第 个大礼包的价格。
返回确切满足购物清单所需花费的最低价格,你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品,即使那样会降低整体价格。任意大礼包可无限次购买。
输入
第一行输入 个整数,前 个数为 数组,最后一个整数为大礼包的数量( 数组的长度)。
接下来 到 行每行 个整数,第 行表示 。
最后一行输入 个整数表示 数组。
题目保证 。
输出
一行输出一个整数表示满足购物清单的最小费用。
样例
标准输入 复制文本 |
2 5 2 3 0 5 1 2 10 3 2 |
标准输出 复制文本 |
14 |
提示
样例一解释:
2 5 2
:前两个是 数组的值 最后一个是 数组的长度 ,即 代表下面的两行都是 数组的值;3 0 5
:代表 的值。1 2 10
:代表 的值。3 2
: 数组的值。答案解释:有 A 和 B 两种物品,价格分别为 和 。大礼包 1,你可以以 的价格购买 个 A 和 个 B;大礼包 2,你可以以 的价格购买 个 A 和 个 B 。
需要购买 个 A 和 个 B,所以付 购买大礼包 2,以及 4 用于另外购买 个 A。