Задача №113252. Робот
В стране Олимпия сегодня праздник! Единственное почтовое отделение на улице Олимпийская переполнено подарками, которые необходимо как можно быстрее доставить их адресатам. Всего в этот день поступило n подарков, i -й из которых необходимо доставить в дом с номером h i . Несколько различных подарков могут быть адресованы в один дом. Почтовое отделение расположено в начале Олимпийской улицы. Справа от почты вдоль прямой дороги находятся дома, нумерация которых начинается с 1 ; i -й дом расположен в i километрах от почты. Для доставки предметов в экспериментальном режиме используется единый специальный почтовый робот, который одновременно вмещает не более k предметов. Загрузка и разгрузка одного подарка длится одну минуту, робот не может загружать и разгружать одновременно. Один километр робот преодолевает тоже за одну минуту.
Напишите программу, которая по информации о каждом из подарков и характеристике робота определяет наименьшее время в минутах, за которое робот сможет доставить все подарки их адресатам и вернуться в почтовое отделение. Сначала все подарки и робот находятся в отделении.
Первая строка входного файла содержит два целых числа n и k ( 1 ≤ n ≤ 100 000 , 1 ≤ k ≤ 1000 ) — количество подарков, поступивших в почтовое отделение, и наибольшее количество предметов, которые робот может одновременно иметь при себе. Вторая строка содержит n целых чисел, записанных через пробел: i -е число равно h i ( 1 ≤ h i ≤ 10 6 ) — номер дома, в который необходимо доставить i -й подарок. Гарантируется, что дома с указанными номерами действительно расположены на Олимпийской улице.
Единственная строка выходного файла должна содержать одно целое число — наименьшее время в минутах, за которое робот сможет доставить подарки их адресатам и вернуться в почтовое отделение.
- 1 ≤ n ≤ 10, 1 ≤ k ≤ 5, 1 ≤ h i ≤ 100 .( 25 баллов)
- 1 ≤ n ≤ 1000, 1 ≤ k ≤ 100, 1 ≤ h i ≤ 10 000 .( 25 баллов)
- 1 ≤ n ≤ 100 000, 1 ≤ k ≤ 1000, 1 ≤ h i ≤ 10 000 .( 25 баллов)
- 1 ≤ n ≤ 100 000, 1 ≤ k ≤ 1000, 1 ≤ h i ≤ 10 6 .( 25 баллов)
7 3 3 9 3 2 1 1 3
40