Pinely Round 3 (Div. 1 + Div. 2) |
---|
Закончено |
У вас есть $$$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)$$$.
Вам не нравятся большие веса, поэтому вы хотите сделать сумму весов всех интервалов как можно меньше. Оказывается, вы можете выполнять следующие три типа операций:
Однако после выполнения всех операций интервалы должны оставаться корректными (т.е. для каждого $$$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$$$.
Для каждого набора входных данных выведите одно целое число: минимально возможную сумму всех весов интервалов после ваших операций.
228 312 23100 100420 1 2 530 4 3 102 3 2 3
2400 42
В первом наборе входных данных вы можете сделать так
В этом случае будет два интервала:
Сумма весов составляет $$$2400$$$. Можно показать, что не существует конфигурации конечных интервалов, сумма весов которых меньше $$$2400$$$.
Во втором наборе входных данных можно сделать так
В этом случае будет четыре интервала:
Сумма весов равна $$$42$$$. Можно показать, что не существует конфигурации конечных интервалов, сумма весов которых меньше $$$42$$$.
Название |
---|