Алёна работает в аэропорту Мегаполиса, составляя расписание отправления рейсов. Сегодня должны отправиться n рейсов, i-й из которых должен вылететь в минуту i.
Как вы помните из задачи вчерашнего дня, аэропорт Мегаполиса является основным транспортным узлом в Метрополии, а в высоконагруженных аэропортах нередко случаются накладки. Ровно так и произошло сегодня — из-за технических неполадок в течение первых k минут ни один рейс не смог вылететь из аэропорта.
Теперь все запланированные n рейсов должны вылететь в различные минуты от (k + 1)-й до (k + n)-й включительно. Однако рейсы не обязаны вылетать в исходном порядке — Алёна может составить любое расписание отправления рейсов. При этом должно быть выполнено важное условие: ни один рейс не может вылететь раньше своего изначально запланированного времени вылета.
Алёна знает, что задержка вылета i-го рейса на одну минуту стоит аэропорту ci бурлей. Помогите Алёне определить, в каком порядке следует вылетать рейсам, чтобы суммарная стоимость задержки оказалась минимально возможной.
Выходные данные
В первой строке выведите минимальную возможную суммарную стоимость задержки всех рейсов.
Во второй строке выведите n различных целых чисел t1, t2, ..., tn (k + 1 ≤ ti ≤ k + n), где ti означает время вылета i-го рейса. Если расписаний с минимальной стоимостью несколько, разрешается вывести любое из них.
Примечание
Рассмотрим пример из условия. Если сдвинуть рейсы на 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 бурлей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
4 2 1 10 2
|
20
3 6 7 4 5
|