← 返回题目列表

Codeforces · 1739/F

F. 键盘设计

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

Monocarp 有一个包含 $$$n$$$ 个单词的字典,由 $$$12$$$ 拉丁字母表的第一个字母组成。单词的编号从 $$$1$$$ 到 $$$n$$$。每个单词中的每一对相邻字符中,字符都是不同的。对于每个单词 $$$i$$$,Monocarp 还有一个整数 $$$c_i$$$ 表示他使用该单词的频率。

Monocarp 希望设计一个键盘,让他可以轻松输入一些单词。键盘可以表示为 $$$12$$$ 拉丁字母表的第一个字母的序列,其中从 a 到 l 的每个字母只出现一次。

如果对于单词中的每对相邻字符,这些字符在键盘中也是相​​邻的,则可以轻松地用键盘键入单词。键盘的最优性是 $$$c_i$$$ 对所有可以轻松输入的单词 $$$i$$$ 的总和。

帮助 Monocarp 设计一款具有最大可能优化性的键盘。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 单词数。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含一个整数 $$$c_i$$$ ($$$1 \le c_i \le 10^5$$$) 和一个字符串 $$$s_i$$$ ($$$2 \le |s_i| \le 2000$$$) 表示第 $$$i$$$ 个单词。 $$$s_i$$$ 的每个字符都是 $$$12$$$ 拉丁字母表的第一个字母,小写。对于 [1, |s_i| 中的每个 $$$j \ - 1]$$$,$$$s_i$$$的第$$$j$$$个字符与第$$$(j+1)$$$个字符不同。

输入的附加约束:$$$\sum \limits_{i=1}^{n} |s_i| \le 2000$$$。

输出

打印 $$$12$$$ 拉丁字母表的第一个字母的序列,其中从 a 到 l 的每个字母只出现一次,表示最佳键盘。如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

3
7 abacaba
10 cba
4 db

输出 #1

hjkildbacefg

输入 #2

1
100 abca

输出 #2

abcdefghijkl