字符串卡片

题目描述

有 $N$ 张卡片,第 $i$ 张卡片上写着字符串 $S_i$。

从中选择 $K$ 张卡片,并以任意顺序拼接,求能得到的所有字符串中字典序最小的一个。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出答案。

样例

4 3
ode
zaaa
r
atc

atcoder

注意,不能反转卡片上写着的字符串,也不能打乱其中的字符顺序。

例如,写在第 1 张卡片上的 ode 不能作为 edo 或 deo 使用。

5 2
z
z
zzz
z
zzzzzz

zz

可能存在 $i, j$($i\neq j$)使得 $S_i = S_j$。

数据范围

• $1 \le K \le N \le 50$
• $1 \le |S_i| \le 50$
• $S_i$ 由小写英文字母组成。

提示

关于字典序:

简单来说,字典序就是单词在字典中的排列顺序。更正式的定义如下,它给出了确定两个不同的字符串 $S$ 和 $T$ 字典序大小的算法。

下面用 $S_i$ 表示 $S$ 的第 $i$ 个字符。另外,如果 $S$ 的字典序小于 $T$,记作 $S \lt T$;如果 $S$ 的字典序大于 $T$,记作 $S \gt T$。

设 $L$ 为 $S$ 和 $T$ 中较短者的长度。对每个 $i=1,2,\dots,L$,检查 $S_i$ 与 $T_i$ 是否相同。

如果存在 $i$ 使得 $S_i \neq T_i$,设 $j$ 为最小的这样的 $i$。然后比较 $S_j$ 和 $T_j$。如果 $S_j$ 在字母表顺序上先于 $T_j$,则判定 $S \lt T$ 并结束;如果 $S_j$ 晚于 $T_j$,则判定 $S \gt T$ 并结束。

如果不存在 $i$ 使得 $S_i \neq T_i$,则比较 $S$ 和 $T$ 的长度。如果 $S$ 比 $T$ 短,判定 $S \lt T$ 并结束;如果 $S$ 比 $T$ 长,判定 $S \gt T$ 并结束。