CF1909C Heavy Intervals

[Shiki - Pure Ruby](https://soundcloud.com/shiki-8/pure-rubyversoundcloud) ⠀ 你有 $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$。

对于每个测试用例，输出一个整数，表示经过操作后所有区间权值和的最小可能值。

在第一个测试用例中，你可以让 - $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$ 更小的权值和的区间配置。 由 ChatGPT 4.1 翻译