← 返回题目列表

Codeforces · 1011/A

A. 阶段

中文机器翻译题面 查看原题

娜塔莎要去火星。她需要建造一枚火箭,该火箭由按某种顺序排列的多个阶段组成。每个阶段都由一个小写拉丁字母定义。这样,火箭就可以用字符串来描述——字母串联,对应于阶段。

有 $$$n$$$ 可用阶段。火箭必须恰好包含 $$$k$$$ 个。火箭中的级应按其重量排序。因此,在带有某个字母的阶段之后只能进入带有一个字母的阶段,该字母在字母表中至少有两个位置(中间跳过一个字母,甚至更多)。例如,字母“c”之后不能接字母“a”、“b”、“c”和“d”,但可以接字母“e”、“f”、...、“z”。

为了让火箭飞得尽可能远,它的重量应该尽可能小。火箭的重量等于其各级重量的总和。舞台的权重是其字母在字母表中的数量。例如,舞台“a”重一吨,“b”重两吨,“z”— $$$26$$$ 吨。

以最小的重量建造火箭,或者确定根本不可能建造火箭。每个阶段最多可以使用一次。

输入

输入的第一行包含两个整数 - $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 50$$$) – 可用级数和火箭中使用的级数。

第二行包含字符串 $$$s$$$,它由 $$$n$$$ 小写拉丁字母组成。每个字母都定义了一个新的阶段,可用于建造火箭。每个阶段最多可以使用一次。

输出

打印一个整数 - 火箭的最小总重量,如果根本不可能建造火箭,则打印 -1。

示例

输入 #1

5 3
xyabd

输出 #1

29

输入 #2

7 4
problem

输出 #2

34

输入 #3

2 2
ab

输出 #3

-1

输入#4

12 1
abaabbaaabbb

输出#4

1

注意

在第一个示例中,以下火箭满足条件:

- “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。