F - 字符串卡片

分数: $500$ 分

问题描述

我们有 $N$ 张卡片。第 $i$ 张卡片上有一个字符串 $S_i$。

找到能通过选择这些卡片中的 $K$ 张并任意拼接它们的方式得到的字典序最小的字符串。

在下面的定义中，用 $S_i$ 表示 $S$ 的第 $i$ 个字符。如果 $S$ 字典序小于 $T$，我们将记为 $S \lt T$；如果 $S$ 字典序大于 $T$，我们将记为 $S \gt T$。

1. 令 $L$ 为 $S$ 和 $T$ 长度中较小的那个。对于每个 $i=1,2,\dots,L$，我们检查 $S_i$ 和 $T_i$ 是否相等。
2. 如果存在一个 $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$ 并退出。
3. 如果不存在 $i$ 使得 $S_i \neq T_i$，我们比较 $S$ 和 $T$ 的长度。如果 $S$ 的长度小于 $T$ 的长度，我们确定 $S \lt T$ 并退出；如果 $S$ 的长度大于 $T$ 的长度，我们确定 $S \gt T$ 并退出。

</details> -->

约束

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

---

输入

输入是标准输入格式，具体如下：

$N$ $K$

$S_1$

$S_2$

$\vdots$

$S_N$

输出

输出答案。

---

4 3
ode
zaaa
r
atc

atcoder

请注意，无法对卡片上的字符串进行翻转或排列。
例如，第一张卡片上写着的 ode 不能变成 edo 或 deo。

---

5 2
z
z
zzz
z
zzzzzz

zz

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