← 返回题目列表

Codeforces · 1909/C

C. 大间隔

中文机器翻译题面 查看原题

您有 $$$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$$$的最终区间配置。