#P18087. VIP Coupon

VIP Coupon

VIP Coupon

题目描述

商店有 nn 件商品和 mm 张 VIP 优惠券。第 ii 件商品的原价为 aia_i,第 jj 张优惠券的原价为 bjb_j,优惠参数为 cjc_j。

购买一张参数为 vv 的优惠券后,紧接着购买的下一个物品的价格从 xx 变为 max⁡(x−v,0)\max(x-v,0)。这个物品既可以是商品,也可以是另一张优惠券。

优惠必须在下一次购买时生效,不能延后、储存或叠加。每件商品和每张优惠券均至多购买一次。购买优惠券时即使享受了前一张券的折扣,它仍会对下一次购买产生自身的优惠效果。

你可以按任意顺序购买所有商品,以及任选任意张优惠券(也可以一张都不买)。求买齐所有商品的最小总花费。

输入格式

第一行一个整数 tt。每组数据包含四行:

  1. 两个整数 n,mn,m。
  2. nn 个整数 a1,…,ana_1,\ldots,a_n。
  3. mm 个整数 b1,…,bmb_1,\ldots,b_m。
  4. mm 个整数 c1,…,cmc_1,\ldots,c_m。

1≤t≤1051\le t\le10^5,1≤n,m≤5⋅1051\le n,m\le5\cdot10^5,0≤ai,bj,cj≤1090\le a_i,b_j,c_j\le10^9。所有组的 n+mn+m 之和不超过 5⋅1055\cdot10^5。

输出格式

每组输出一行一个整数,表示最小总花费。

样例输入

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