CF1739F.Keyboard Design

Monocarp has a dictionary of $n$ words, consisting of $12$ first letters of the Latin alphabet. The words are numbered from $1$ to $n$. In every pair of adjacent characters in each word, the characters are different. For every word $i$, Monocarp also has an integer $c_i$ denoting how often he uses this word.

Monocarp wants to design a keyboard that would allow him to type some of the words easily. A keyboard can be denoted as a sequence of $12$ first letters of the Latin alphabet, where each letter from a to l appears exactly once.

A word can be typed with the keyboard easily if, for every pair of adjacent characters in the word, these characters are adjacent in the keyboard as well. The optimality of the keyboard is the sum of $c_i$ over all words $i$ that can be typed easily with it.

Help Monocarp to design a keyboard with the maximum possible optimality.

Monocarp 拥有一个包含 $n$ 个单词的词典，这些单词仅由拉丁字母表的前 $12$ 个字母（即 a 到 l）组成。这些单词编号为 $1$ 至 $n$。在每个单词中，任意两个相邻字符均不相同。

对于每个单词 $i$，Monocarp 还拥有一个整数 $c_i$，表示他使用该单词的频率。

Monocarp 希望设计一款键盘，使得他能便捷地输入其中一部分单词。键盘可表示为一个长度为 $12$ 的序列，恰好包含字母 a 到 l 各一次。

若一个单词中每一对相邻字符在键盘序列中也彼此相邻，则称该单词可被此键盘“便捷输入”。键盘的“最优性”定义为：所有可被便捷输入的单词 $i$ 对应的 $c_i$ 值之和。

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

The first line contains one integer $n$ ($1 \le n \le 1000$) — the number of words.

Then, $n$ lines follow. The $i$-th of them contains an integer $c_i$ ($1 \le c_i \le 10^5$) and a string $s_i$ ($2 \le |s_i| \le 2000$) denoting the $i$-th word. Each character of $s_i$ is one of $12$ first letters of Latin alphabet, in lowercase. For every $j \in [1, |s_i| - 1]$, the $j$-th character of $s_i$ is different from the $(j+1)$-th one.

Additional constraint on the input: $\sum \limits_{i=1}^{n} |s_i| \le 2000$.

第一行包含一个整数 $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$ 个小写字母之一。对每个 $j \in [1, |s_i| - 1]$，$s_i$ 的第 $j$ 个字符与第 $(j+1)$ 个字符不同。

输入的额外约束：$\sum \limits_{i=1}^{n} |s_i| \le 2000$。

Print a sequence of $12$ first letters of the Latin alphabet, where each letter from a to l appears exactly once, denoting the optimal keyboard. If there are multiple answers, you may print any of them.

输出拉丁字母表的前 $12$ 个字母构成的一个序列，其中每个字母 a 到 l 恰好出现一次，表示最优键盘布局。如果存在多个答案，输出任意一个即可。