您有 $$$n$$$ 间隔 $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$,这样每个 $$$i$$$ 的 $$$l_i < r_i$$$,并且间隔的所有端点都是不同的。
第 $$$i$$$ 个间隔每单位长度的权重为 $$$c_i$$$。因此,第 $$$i$$$ 个区间的权重为 $$$c_i \cdot (r_i - l_i)$$$。
您不喜欢大的权重,因此您希望使间隔的权重总和尽可能小。事实证明,您可以执行以下所有三个操作:
- 以任意顺序重新排列数组 $$$l$$$ 中的元素;
- 以任意顺序重新排列数组 $$$r$$$ 中的元素;
- 以任意顺序重新排列数组 $$$c$$$ 中的元素。
然而,执行完所有操作后,间隔必须仍然有效(即,对于每个 $$$i$$$,$$$l_i < r_i$$$ 必须成立)。
执行操作后,区间权重的最小可能总和是多少?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 间隔数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i \le 2 \cdot 10^5$$$) - 初始间隔的左端点。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$r_1, r_2, \ldots, r_n$$$ ($$$l_i < r_i \le 2 \cdot 10^5$$$) - 初始间隔的右端点。
保证 $$$\{l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n\}$$$ 都是不同的。
每个测试用例的第四行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^7$$$) — 每单位长度间隔的初始权重。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数:操作后区间权重的最小可能总和。
示例
输入 #1
2 2 8 3 12 23 100 100 4 20 1 2 5 30 4 3 10 2 3 2 3
输出 #1
2400 42
注意
在第一个测试用例中,您可以使
- $$$l = [8, 3]$$$;
- $$$r = [23, 12]$$$;
- $$$c = [100, 100]$$$。
在这种情况下,有两个间隔:
- 间隔 $$$[8, 23]$$$,每单位长度重量为 $$$100$$$,总计 $$$100 \cdot (23-8) = 1500$$$;
- 间隔 $$$[3, 12]$$$,每单位长度权重 $$$100$$$,总计 $$$100 \cdot (12-3) = 900$$$。
权重总和为 $$$2400$$$。可以看出,不存在权重总和小于$$$2400$$$的最终区间配置。
在第二个测试用例中,您可以使
- $$$l = [1, 2, 5, 20]$$$;
- $$$r = [3, 4, 10, 30]$$$;
- $$$c = [3, 3, 2, 2]$$$。
在这种情况下,有四个间隔:
- 间隔 $$$[1, 3]$$$,每单位长度的权重为 $$$3$$$,总共 $$$3 \cdot (3-1) = 6$$$;
- 间隔 $$$[2, 4]$$$,每单位长度重量 $$$3$$$,总共 $$$3 \cdot (4-2) = 6$$$;
- 间隔 $$$[5, 10]$$$,每单位长度权重 $$$2$$$,总计 $$$2 \cdot (10-5) = 10$$$;
- 间隔 $$$[20, 30]$$$,每单位长度权重 $$$2$$$,总计 $$$2 \cdot (30-20) = 20$$$。
权重总和为 $$$42$$$。可以看出,不存在权重总和小于$$$42$$$的最终区间配置。