Вы — кот, продающий интересные алгоритмические задачи. Сегодня вы хотите прорекламировать свои интересные алгоритмические задачи в \(k\) городах.
Всего есть \(n\) городов, каждый из которых имеет два параметра \(a_i\) и \(b_i\). Между любыми двумя городами \(i,j\) (\(i\ne j\)) есть двусторонняя дорога длиной \(\max(a_i + b_j , b_i + a_j)\). Стоимость пути определяется как сумма длин дорог между каждыми двумя соседними городами вдоль пути.
Для \(k=2,3,\ldots,n\) найдите минимальную стоимость среди всех простых путей, содержащих ровно \(k\) различных городов.
Выходные данные
Для каждого набора входных данных выведите \(n-1\) целых числа в одной строке. \(i\)-е целое число представляет собой минимальную стоимость при \(k=i+1\).
Примечание
В первом наборе входных данных:
- Для \(k=2\) оптимальный путь: \(1\to 2\) со стоимостью \(\max(0+1,2+2)=4\).
- Для \(k=3\) оптимальный путь: \(2\to 1\to 3\) со стоимостью \(\max(0+1,2+2)+\max(0+3,3+2)=4+5=9\).
Во втором наборе входных данных:
- Для \(k=2\) оптимальный путь: \(1\to 4\).
- Для \(k=3\) оптимальный путь: \(2\to 3\to 5\).
- Для \(k=4\) оптимальный путь: \(4\to 1\to 3\to 5\).
- Для \(k=5\) оптимальный путь: \(5\to 2\to 3\to 1\to 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
0 2
2 1
3 3
5
2 7
7 5
6 3
1 8
7 5
8
899167687 609615846
851467150 45726720
931502759 23784096
918190644 196992738
142090421 475722765
409556751 726971942
513558832 998277529
294328304 434714258
|
4 9
10 22 34 46
770051069 1655330585 2931719265 3918741472 5033924854 6425541981 7934325514
|