E. Выбираем точки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют с точками на плоскости XY. Первоначально, на плоскости отмечены $$$n$$$ точек: $$$i$$$-я точка расположена в $$$(x_i, y_i)$$$ и имеет стоимость $$$c_i$$$.

Игра состоит из двух этапов:

  1. Сначала Алиса выбирает некоторые точки (возможно, ни одной, но не все) и удаляет их с поля.
  2. Далее Боб рисует прямоугольник, параллельный осям координат, так, чтобы все оставшиеся точки лежали внутри или на границе этого прямоугольника. Прямоугольник может вырождаться в отрезок или даже точку.

После этого игра заканчивается и подсчитывается общий счет. Общий счет игры складывается из суммы стоимостей удаленных Алисой точек и длины периметра прямоугольника, нарисованного Бобом. При этом Алиса стремится максимизировать счет, а Боб — минимизировать.

Определите общий счет игры, если и Алиса, и Боб будут действовать оптимально.

Периметр прямоугольника равен сумме длин всех его четырех сторон. Поэтому, даже если прямоугольник выродился в отрезок длины $$$k$$$, его периметр будет равен $$$2k$$$. Периметр прямоугольника, выродившегося в точку, равен $$$0$$$.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — исходное количество точек на плоскости.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le 10^{15}$$$) — $$$x$$$-координаты точек.

В третьей строке заданы $$$n$$$ целых чисел $$$y_1, y_2, \dots, y_n$$$ ($$$0 \le y_i \le 10^{15}$$$) — $$$y$$$-координаты точек.

В четвертой строке заданы $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 10^9$$$) — стоимости точек.

Дополнительные ограничения на входные данные:

  • в одном наборе входных данных все точки попарно различны;
  • суммарное количество точек по всем наборам не превосходит $$$3 \cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите единственное число — итоговый счет игры, если и Алиса, и Боб играют оптимально.

Пример
Входные данные
4
1
42
42
1000
4
5 10 5 0
0 5 10 5
1 1 1 1
4
6 7 8 9
3 3 3 3
9 0 9 0
2
1000000000 10
10 1000000000
12345 54321
Выходные данные
0
40
22
3999999960
Примечание

В первом наборе входных данных всего одна точка, и Алиса не может удалить ее. Тогда Боб строит прямоугольник $$$(1, 1) - (1, 1)$$$ с периметром $$$0$$$.

Во втором наборе входных данных Алисе выгодно не удалять ни одной точки. Тогда Боб строит прямоугольник $$$(0, 0) - (10, 10)$$$ с периметром $$$40$$$.

В третьем наборе Алисе выгодно удалить первую и третью точки. Тогда Боб строит прямоугольник $$$(7, 3) - (9, 3)$$$ с периметром $$$4$$$. Общий счет будет равен $$$9 + 9 + 4 = 22$$$.