Наташа собирается полететь на Марс. Ей необходимо построить ракету, которая собирается из нескольких ступеней в определённом порядке. Каждая из ступеней описывается одной строчной буквой латинского алфавита. Тем самым ракета описывается строкой — конкатенацией букв, соответствующих ступеням.
Всего на складе есть \(n\) ступеней. Ракета должна содержать ровно \(k\) из них. Ступени в ракете должны быть упорядочены по весу. После ступени с некоторой буквой можно ставить только ступень с буквой, идущей хотя бы на две позиции позже в алфавите (то есть через одну букву или более). Например, после буквы 'c' нельзя ставить буквы 'a', 'b', 'c' и 'd', зато можно ставить 'e', 'f', ..., 'z'.
Чтобы ракета летела максимально далеко, нужно, чтобы её вес был минимален. Вес ракеты равен сумме весов её ступеней. Ступень весит столько тонн, каков номер её буквы в алфавите. Иными словами, ступень 'a' весит одну тонну, 'b' весит две тонны, а 'z' — \(26\) тонн.
Постройте ракету минимального веса или скажите, что ни одной ракеты построить нельзя. Каждую из ступеней на складе можно использовать не более одного раза.
Примечание
В первом примере условию удовлетворяют такие ракеты:
- «adx» (вес равен \(1+4+24=29\));
- «ady» (вес равен \(1+4+25=30\));
- «bdx» (вес равен \(2+4+24=30\));
- «bdy» (вес равен \(2+4+25=31\)).
Минимальный вес имеет ракета «adx», следовательно ответ равен \(29\).
Во втором примере искомая ракета — «belo». Её вес — \(2+5+12+15=34\).
В третьем примере \(n=k=2\), поэтому ракета должна содержать обе ступени: 'a' и 'b'. Такая ракета не удовлетворяет условию, поскольку эти буквы стоят в алфавите рядом. Ответ — -1.