В компьютерном классе стоят два ряда компьютеров. В каждом ряду ровно по \(n\) компьютеров и у компьютеров есть своя классификация. Компьютеры в первом ряду имеют классы \(a_1, a_2, \dots, a_n\), а компьютеры во втором ряду — \(b_1, b_2, \dots, b_n\).
Первоначально, все пары соседних компьютеров в каждом ряду соединены кабелем (пары \((i, i + 1)\) для всех \(1 \le i < n\)), а потому ряды образуют две независимые компьютерные сети.
Ваша задача — объединить их в одну общую сеть посредством соединения одной или более пар компьютеров с разных рядов. Соединение \(i\)-го компьютера с первого ряда и \(j\)-го компьютера второго ряда стоит \(|a_i - b_j|\).
Вы можете соединять один компьютер с несколькими другими, но вам нужно обеспечить хотя бы базовую отказоустойчивость: вам нужно соединить компьютеры таким образом, чтобы сеть осталась цельной, даже если один из компьютеров будет уничтожен. Другими словами, какой бы один компьютер не был выведен из строя, сеть не развалится на несколько несвязанных частей.
Чему равна наименьшая стоимость построить отказоустойчивую сеть?
Выходные данные
Для каждого набора входных данных выведите одно число — минимальную суммарную стоимость построить отказоустойчивую сеть.
Примечание
В первом наборе входных данных, выгодно соединить четыре пары компьютеров:
- компьютер \(1\) на первом ряду и компьютер \(2\) на втором ряду: стоимость равна \(|1 - 4| = 3\);
- компьютер \(3\) на первом ряду и компьютер \(2\) на втором ряду: стоимость \(|1 - 4| = 3\);
- компьютер \(2\) на первом ряду и компьютер \(1\) на втором ряду: стоимость \(|10 - 20| = 10\);
- компьютер \(2\) на первом ряду и компьютер \(3\) на втором ряду: стоимость \(|10 - 25| = 15\);
В сумме,
\(3 + 3 + 10 + 15 = 31\).
Во втором наборе, выгодно соединить \(1\) на первом ряду и \(1\) на втором ряду, а также \(4\) на первом ряду и \(4\) на втором.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
1 10 1
20 4 25
4
1 1 1 1
1000000000 1000000000 1000000000 1000000000
|
31
1999999998
|