题目描述

给定一个仅由小写英文字母组成的字符串 $s$。

如果字符串 $t$ 中每种字母的出现次数都与 $s$ 中相同，则称 $t$ 是 $s$ 的一个重排。定义 $t$ 的相邻代价为

$$\operatorname{cost}(t)=\left|\{i\mid 1\le i<|t|,\ t_i=t_{i+1}\}\right|.$$

也就是说，每一对相同的相邻字母会产生 $1$ 的代价。

你需要找到一个相邻代价不超过 $k$ 的重排，并使它的字典序最小。如果不存在这样的重排，输出 -1。

两个等长字符串的字典序按如下方式比较：在第一个不同的位置上，字母更小的字符串字典序更小，其中 a 到 z 依次增大。

输入格式

从文件 budget.in 中读取数据。

第一行输入两个整数 $n,k$，分别表示字符串长度和允许的最大相邻代价。

第二行输入一个长度为 $n$ 的字符串 $s$。

输出格式

输出到文件 budget.out 中。

如果不存在符合要求的重排，输出一行 -1。

否则，输出一行一个字符串，表示字典序最小的、相邻代价不超过 $k$ 的重排。

6 1
aaabbc

aababc

5 0
aaaab

-1

样例解释

样例 #1 中，aababc 恰好含有一对相同的相邻字母。任何以 aaa 开头的字符串都已经产生至少 $2$ 的相邻代价，因此答案不能比它更早出现第三个 a；继续比较后可得样例所示字符串为字典序最小的可行重排。

样例 #2 中，唯一的 b 最多把四个 a 分成两段，因此无论怎样重排，都至少有两对相同的相邻字母。

数据规模与约定

对于所有数据，保证：

• $1\le n\le 10^5$；
• $0\le k<n$；
• $s$ 的长度为 $n$，且仅由小写英文字母组成。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数；各子任务独立计分。

子任务对应的测试点编号	分值	约束
$1\sim 4$	$20$	$n\le 10$
$5\sim 8$		$s$ 仅由 a、b 组成
$9\sim 13$	$25$	$k=0$
$14\sim 20$	$35$	无特殊限制

下发文件

下载三组测试数据，非真实测试数据