A. Балансировка массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам заданы два массива длины $$$n$$$: $$$a_1, a_2, \dots, a_n$$$ и $$$b_1, b_2, \dots, b_n$$$.

Вы можете применить к ним следующую операцию произвольное количество раз:

  1. Выбрать позицию $$$i$$$ ($$$1 \le i \le n$$$);
  2. Поменять местами $$$a_i$$$ и $$$b_i$$$.

Чему равна наименьшая возможная сумма $$$|a_1 - a_2| + |a_2 - a_3| + \dots + |a_{n-1} - a_n|$$$ $$$+$$$ $$$|b_1 - b_2| + |b_2 - b_3| + \dots + |b_{n-1} - b_n|$$$ (другими словами, $$$\sum\limits_{i=1}^{n - 1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}$$$), которую можно получить после применения заданной операции произвольное количество раз (возможно, ни разу)?

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

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

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \le n \le 25$$$) — длина массивов $$$a$$$ и $$$b$$$.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив $$$a$$$.

В третьей строке каждого набора заданы $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — массив $$$b$$$.

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

Для каждого набора входных данных выведите одно целое число — наименьшую возможную сумму $$$\sum\limits_{i=1}^{n-1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}$$$.

Пример
Входные данные
3
4
3 3 10 10
10 10 3 3
5
1 2 3 4 5
6 7 8 9 10
6
72 101 108 108 111 44
10 87 111 114 108 100
Выходные данные
0
8
218
Примечание

В первом наборе входных данных мы можем, например, поменять местами $$$a_3$$$ с $$$b_3$$$ и $$$a_4$$$ с $$$b_4$$$. Мы получим массивы $$$a = [3, 3, 3, 3]$$$ и $$$b = [10, 10, 10, 10]$$$ с суммой $$$3 \cdot |3 - 3| + 3 \cdot |10 - 10| = 0$$$.

Во втором наборе массивы уже имеют наименьшую сумму (описанную ранее), равную $$$|1 - 2| + \dots + |4 - 5| + |6 - 7| + \dots + |9 - 10|$$$ $$$= 4 + 4 = 8$$$.

В третьем наборе мы можем, например, поменять местами $$$a_5$$$ с $$$b_5$$$.