Stages

题意翻译

定义一个长度为$n$的字符串$s$的价值为 $ \sum\limits_{i=1}^{n}{}(s[i]-'a'+1)$ 定义一个长度为 $n$ 的字符串 $s$ 是优秀的，当且仅当 $\forall x \in [1,n-1] (s[x]-'a')<(s[x+1]-'a'-1)$ 在给出一个长度为 $n$字符串 $t$，求在从 $t$ 中选 $k$ 个字符所能组成的所有优秀的字符串中价值最低的的价值，如果不能构造出优秀的序列，输出 $-1$。 ## 输入输出格式 ### 输入格式 第一行两个整数，$n$和$k(1\le k \le n \le 50)$； 第二行一个字符串$t$，保证$t$只由小写字母组成。 ### 输出格式 一个整数，即最低价值。

题目描述

Natasha is going to fly to Mars. She needs to build a rocket, which consists of several stages in some order. Each of the stages is defined by a lowercase Latin letter. This way, the rocket can be described by the string — concatenation of letters, which correspond to the stages. There are $ n $ stages available. The rocket must contain exactly $ k $ of them. Stages in the rocket should be ordered by their weight. So, after the stage with some letter can go only stage with a letter, which is at least two positions after in the alphabet (skipping one letter in between, or even more). For example, after letter 'c' can't go letters 'a', 'b', 'c' and 'd', but can go letters 'e', 'f', ..., 'z'. For the rocket to fly as far as possible, its weight should be minimal. The weight of the rocket is equal to the sum of the weights of its stages. The weight of the stage is the number of its letter in the alphabet. For example, the stage 'a 'weighs one ton,' b 'weighs two tons, and' z' — $ 26 $ tons. Build the rocket with the minimal weight or determine, that it is impossible to build a rocket at all. Each stage can be used at most once.

输入输出格式

输入格式

The first line of input contains two integers — $ n $ and $ k $ ( $ 1 \le k \le n \le 50 $ ) – the number of available stages and the number of stages to use in the rocket. The second line contains string $ s $ , which consists of exactly $ n $ lowercase Latin letters. Each letter defines a new stage, which can be used to build the rocket. Each stage can be used at most once.

输出格式

Print a single integer — the minimal total weight of the rocket or -1, if it is impossible to build the rocket at all.

输入输出样例

输入样例 #1

5 3
xyabd

输出样例 #1

29

输入样例 #2

7 4
problem

输出样例 #2

34

输入样例 #3

2 2
ab

输出样例 #3

-1

输入样例 #4

12 1
abaabbaaabbb

输出样例 #4

1

说明

In the first example, the following rockets satisfy the condition: - "adx" (weight is $ 1+4+24=29 $ ); - "ady" (weight is $ 1+4+25=30 $ ); - "bdx" (weight is $ 2+4+24=30 $ ); - "bdy" (weight is $ 2+4+25=31 $ ). Rocket "adx" has the minimal weight, so the answer is $ 29 $ . In the second example, target rocket is "belo". Its weight is $ 2+5+12+15=34 $ . In the third example, $ n=k=2 $ , so the rocket must have both stages: 'a' and 'b'. This rocket doesn't satisfy the condition, because these letters are adjacent in the alphabet. Answer is -1.

题意翻译

定义一个长度为 $n$ 的字符串 $s$ 的价值为 $\sum\limits_{i=1}^n(s_i-\texttt{'a'})$。 定义一个长度为 $n$ 的字符串 $s$ 是优秀的，当且仅当 $\forall x\in[1,n-1], (s_x-\texttt{'a'})<(s_{x+1}-\texttt{'a'} - 1)$。 再给出一个长度为 $n$ 的字符串 $t$，求在 $t$ 中选 $k$ 个字符能够组成的所有优秀的字符串中的最少价值。如果不能构造出优秀的字符串，请输出 $-1$。