Задача №3782. Abcdefg (малые ограничения)
Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N-й символы алфавита использованы в сообщении f1, f2, ..., fN раз. Его необходимо набрать на M-клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.
На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.
В нашем случае, символы с 1-ого по некоторый K1-ый должны соответствовать 1-ой клавише, с (K1 + 1)-ого по некоторый K2-ой — 2-ой клавише и т. д., до KM = N. Конкретные значения K1, K2, ..., KM - 1 не задаются — их, наоборот, нужно подобрать.
Напишите программу, которая будет искать минимальное необходимое количество нажатий на клавиши для набора указанного сообщения на указанной клавиатуре.
В первой строке содержатся два числа N и M, во второй — N чисел f1, f2, ..., fN — количества вхождений соответствующего символа. Числа внутри строк разделены одинарными пробелами. 2 ≤ M ≤ 50, 3 ≤ N ≤ 70, M < N, 1 ≤ fi ≤ 1000.
Необходимо вывести единственное число — найденное минимальное количество нажатий на клавиши.
Значение 21 достигается при K1 = 2, K2 = 3 (1-й и 2-й символы сопоставить 1-й клавише, 3-й символ 2-й клавише, 4-й и 5-й символы 3-й клавише). Тогда количество нажатий будет
(3 × 1 + 2 × 2) + (5 × 1) + (7 × 1 + 1 × 2) = 21.
5 3 3 2 5 7 1
21