A. Вопросы планирования
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алёна работает в аэропорту Мегаполиса, составляя расписание отправления рейсов. Сегодня должны отправиться n рейсов, i-й из которых должен вылететь в минуту i.

Как вы помните из задачи вчерашнего дня, аэропорт Мегаполиса является основным транспортным узлом в Метрополии, а в высоконагруженных аэропортах нередко случаются накладки. Ровно так и произошло сегодня — из-за технических неполадок в течение первых k минут ни один рейс не смог вылететь из аэропорта.

Теперь все запланированные n рейсов должны вылететь в различные минуты от (k + 1)-й до (k + n)-й включительно. Однако рейсы не обязаны вылетать в исходном порядке — Алёна может составить любое расписание отправления рейсов. При этом должно быть выполнено важное условие: ни один рейс не может вылететь раньше своего изначально запланированного времени вылета.

Алёна знает, что задержка вылета i-го рейса на одну минуту стоит аэропорту ci бурлей. Помогите Алёне определить, в каком порядке следует вылетать рейсам, чтобы суммарная стоимость задержки оказалась минимально возможной.

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

В первой строке входных данных находятся два целых числа n и k (1 ≤ k ≤ n ≤ 300 000), где n — количество рейсов, а k — количество минут, в течение которых рейсы не вылетали из аэропорта.

Во второй строке находятся n чисел c1, c2, ..., cn (1 ≤ ci ≤ 107), где ci — стоимость задержки i-го рейса на одну минуту.

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

В первой строке выведите минимальную возможную суммарную стоимость задержки всех рейсов.

Во второй строке выведите n различных целых чисел t1, t2, ..., tn (k + 1 ≤ ti ≤ k + n), где ti означает время вылета i-го рейса. Если расписаний с минимальной стоимостью несколько, разрешается вывести любое из них.

Пример
Входные данные
5 2
4 2 1 10 2
Выходные данные
20
3 6 7 4 5
Примечание

Рассмотрим пример из условия. Если сдвинуть рейсы на 2 минуты, сохранив их порядок вылета, то суммарная стоимость задержки всех рейсов составит (3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38 бурлей.

Если же изменить расписание так, как показано в ответе, то суммарная стоимость составит (3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20 бурлей.