#P18087. VIP Coupon
VIP Coupon
VIP Coupon
题目描述
商店有 件商品和 张 VIP 优惠券。第 件商品的原价为 ,第 张优惠券的原价为 ,优惠参数为 。
购买一张参数为 的优惠券后,紧接着购买的下一个物品的价格从 变为 。这个物品既可以是商品,也可以是另一张优惠券。
优惠必须在下一次购买时生效,不能延后、储存或叠加。每件商品和每张优惠券均至多购买一次。购买优惠券时即使享受了前一张券的折扣,它仍会对下一次购买产生自身的优惠效果。
你可以按任意顺序购买所有商品,以及任选任意张优惠券(也可以一张都不买)。求买齐所有商品的最小总花费。
输入格式
第一行一个整数 。每组数据包含四行:
- 两个整数 。
- 个整数 。
- 个整数 。
- 个整数 。
,,。所有组的 之和不超过 。
输出格式
每组输出一行一个整数,表示最小总花费。
样例输入
2
2 4
4 7
1 3 2 4
5 2 6 5
3 3
2 3 8
0 5 2
4 7 5
样例输出
4
5