P17302 [ICPC 2026 Xi'an I] VIP Coupon

长安城给 Yuki 留下了许多美好的印象，因此 Yuki 来到了一家商店，打算买一些纪念品带回家。 这家商店一共出售 $n$ 个纪念品和 $m$ 张 VIP 优惠券，第 $i$ 个纪念品的价格为 $a_i$，第 $j$ 张 VIP 优惠券的价格为 $b_j$，参数为 $c_j$。其中，一张参数为 $v$ 的 VIP 优惠券的效果为： - 设购买该优惠券后，下一次购买的物品（包括纪念品和 VIP 优惠券）的价格为 $x$，则该物品的价格会变为 $\max(x - v, 0)$。 VIP 优惠券的效果会强制在下一次购买时生效，不能自主选择使用时间。显然，根据此规则，VIP 优惠券的效果也无法叠加。每个物品（包括纪念品和 VIP 优惠券）**只能购买至多一次**，不能重复购买。 现在，Yuki 打算按照任意顺序购买所有纪念品和任意张 VIP 优惠券（可以为 $0$ 张）。你需要帮助 Yuki 求出，买下所有纪念品的最小花费。

本题包含多组测试数据。 第一行包含一个正整数 $t$ $(1 \le t \le 10^5)$，表示测试数据组数。 对于每组测试数据： - 第一行包含两个正整数 $n, m$ $(1 \le n, m \le 5 \cdot 10^5)$。 - 第二行包含 $n$ 个整数 $a_1, \dots, a_n$ $(0 \le a_i \le 10^9)$。 - 第三行包含 $m$ 个整数 $b_1, \dots, b_m$ $(0 \le b_i \le 10^9)$。 - 第四行包含 $m$ 个整数 $c_1, \dots, c_m$ $(0 \le c_i \le 10^9)$。 保证所有测试数据中 $n$ 和 $m$ 的总和均不超过 $5 \cdot 10^5$。

对于每组测试数据，输出一行，包含一个整数，表示买下所有纪念品的最小花费。

对于第 $1$ 组测试数据： - Yuki 可以依次购买第 $1$ 张优惠券，第 $1$ 个纪念品，第 $3$ 张优惠券，第 $2$ 个纪念品。 - 在优惠后，第 $1$ 个纪念品的价格变为了 $0$，第 $2$ 个纪念品的价格变为了 $1$，总花费为 $1 + 0 + 2 + 1 = 4$。 对于第 $2$ 组测试数据： - Yuki 可以依次购买第 $1$ 个纪念品，第 $1$ 张优惠券，第 $2$ 个纪念品，第 $3$ 张优惠券，第 $2$ 张优惠券，第 $3$ 个纪念品。 - 在优惠后，第 $2$ 个纪念品的价格变为了 $0$，第 $2$ 张优惠券的价格变为了 $0$，第 $3$ 个纪念品的价格变为了 $1$，总花费为 $2 + 0 + 0 + 2 + 0 + 1 = 5$。