题目描述

长安城给 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$。

输出格式

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

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

提示

对于第 $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$。