В последние годы всё более популярными становятся двигатели, работающие на солнечных батареях. В ближайшие дни даже планируется организовать полёт самолёта вокруг земного шара с использованием только солнечной энергии!

Подготовка кругосветного перелёта самолёта на солнечных батареях включает в себя ряд испытательных полётов. Во время каждого испытательного полёта самолёт стартует из некоторого аэродрома A_i и по кратчайшему маршруту летит к аэродрому A_i + 1. Таким образом, за исключением первого полёта самолёт всегда вылетает из аэродрома, в котором закончился предыдущий испытательный полёт.

Известно, что аэродромы, на которых проводятся испытательные полёты, расположены строго в линию от 1-го до N-го. Для каждой пары соседних аэродромов, согласно метеоусловиям и расстоянию между ними, известна дельта энергии Δ Q_{i, i + 1}, которая затрачивается (если Δ Q_{i, i + 1} < 0) или приобретается (если Δ Q_{i, i + 1} ≥ 0) самолётом при перелете между ними. При перелёте между любой парой аэродромов u и v, не являющихся соседними, дельта энергии определяется по формуле:

Вам необходимо найти любую последовательность A из K номеров различных аэродромов такую, что сумма модулей дельт энергии S при перелётах между аэродромами в порядке, заданном этой последовательностью, была наименьшей.