C. Тяжелые интервалы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Shiki - Pure Ruby
⠀

У вас есть $$$n$$$ интервалов $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$ таких, что $$$l_i < r_i$$$ для каждого $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: минимально возможную сумму всех весов интервалов после ваших операций.

Пример
Входные данные
2
2
8 3
12 23
100 100
4
20 1 2 5
30 4 3 10
2 3 2 3
Выходные данные
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$$$.