На числовой прямой расположены \(n\) складов. Склад номер \(i\) находится в точке \(x_i\) для всех \(1 \le i \le n\).
У вас есть \(n\) коробок с товарами, которые нужно доставить по одной в каждый из \(n\) складов. Вы и все \(n\) коробок изначально находитесь в начале координат, точке \(0\). Одновременно вы можете переносить не более \(k\) коробок. Вы должны брать по несколько коробок из начала координат, доставлять их по складам, и возвращаться в начало координат для следующей партии коробок.
Вычислите минимальное расстояние, которое вам нужно пройти, чтобы доставить все коробки по складам. Вы не обязаны возвращаться в начало координат после того, как доставите все коробки.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное расстояние, которое вы должны пройти, чтобы доставить все коробки по складам.
Примечание
В первом примере вы можете носить только по одной коробке. Поэтому один из путей, минимизирующий расстояние, такой: \(0 \to 2 \to 0 \to 4 \to 0 \to 3 \to 0 \to 1 \to 0 \to 5\), где каждый \(0\) обозначает, что вы идете в начало координат и забираете одну коробку, а каждое положительное число означает доставку коробки в склад в соответствующей координате. Общее расстояние равно \(25\). Существуют и другие оптимальные решения.
Во втором примере одно из оптимальных решение такое: \(0 \to 6 \to 8 \to 7 \to 0 \to 5 \to 4 \to 3 \to 0 \to (-5) \to (-10) \to (-15)\), общее расстояние равно \(41\). Можно показать, что \(41\) — минимальное возможное расстояние в этом примере.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 1
1 2 3 4 5
9 3
-5 -10 -15 6 5 8 3 7 4
5 3
2 2 3 3 3
4 2
1000000000 1000000000 1000000000 1000000000
|
25
41
7
3000000000
|