Год Коровы
Год Коровы
Известно, знаки зодиака в Китайском календаре следуют 12-летнему циклу: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, и затем опять Ox. Менее известен тот факт, что в конце каждого года Ox открывается временной портал, позволяющий коровам переместиться в любой другой год Ox в прошлом или будущем.
Корова Беси хочет посетить n своих предшественников, которые жили много раньше.
К несчастью, путешествия во времени утомительны, и Беси предпочитает сделать не более k прыжков во времени. Помогите Беси определить минимальное количество лет, которое потребуется Беси, чтобы посетить всех предшественников и вернуться в текущий год, совершив не более k прыжков во времени по пути.
Беси не обязана использовать временной потрал в данном году Ox, если не хочет. Временные порталы соединяют первые дни каждого из Ox годов друг с другом, поэтому, например, если Беси использовала временной портал и затем подождала 12 лет следующего временного портала, она потратит ровно 12 лет на процесс. Беси начинает свое путешествие в первый день текущего Ox-года, поэтому она может путешествовать назад. Никто из предшественников Беси не жил в годах Ox.
Входные данные
Первая строка ввода содержит n (1 ≤ n ≤ 0x10000, 0x10000 - это число в 16-ричной системе счисления, что равно 65536 в десятичной) и k (1 ≤ k ≤ n). Следующие n строк содержат n различных целых чисел в интервале 1..109
, указывающих сколько лет назад жил каждый из предшественников Беси.
Выходные данные
Выведите минимальное количество лет, которое потребуется Беси, чтобы посетить всех своих предшественников и вернуться в настоящий год.
Пример
Один из способов для Беси посетить всех своих предшественников за 36 лет таков:
- Войти в портал в текущем году и вернуться на 48 лет в прошлое.
- Подождать 12 лет затем войтив портал в 36 лет в прошлом и пропутешествовать 108 лет в прошлое.
- Подождать 24 года, затем зайти в портал в 84 года в прошлом и пропутешествовать обратно в текущий год.
5 3 101 85 100 46 95
36