CF1739F Keyboard Design

Monocarp 有一个包含 $n$ 个单词的词典，这些单词仅由拉丁字母表前 $12$ 个字母组成。单词编号从 $1$ 到 $n$。在每个单词中，任意一对相邻字符都不相同。对于每个单词 $i$，Monocarp 还有一个整数 $c_i$，表示他使用该单词的频率。 Monocarp 想要设计一个键盘，使得他能够更容易地输入其中的一些单词。一个键盘可以表示为拉丁字母表前 $12$ 个字母的一个排列，其中每个字母从 a 到 l 恰好出现一次。 如果对于某个单词的每一对相邻字符，这两个字符在键盘上也是相邻的，那么这个单词就可以被该键盘“轻松输入”。键盘的最优性定义为所有可以被轻松输入的单词的 $c_i$ 之和。 请帮助 Monocarp 设计一个最优性的最大可能值的键盘。

第一行包含一个整数 $n$（$1 \le n \le 1000$），表示单词的数量。 接下来 $n$ 行，每行包含一个整数 $c_i$（$1 \le c_i \le 10^5$）和一个字符串 $s_i$（$2 \le |s_i| \le 2000$），表示第 $i$ 个单词。$s_i$ 的每个字符都是小写的拉丁字母表前 $12$ 个字母之一。对于每个 $j \in [1, |s_i| - 1]$，$s_i$ 的第 $j$ 个字符与第 $j+1$ 个字符不同。 额外输入限制：$\sum \limits_{i=1}^{n} |s_i| \le 2000$。

输出一行，包含拉丁字母表前 $12$ 个字母的一个排列，每个字母从 a 到 l 恰好出现一次，表示最优的键盘。如果有多种答案，可以输出任意一种。

由 ChatGPT 4.1 翻译