Keyboard Design

题意翻译

## 题目描述 $Monocarp$有一本$n$个单词组成的字典，由$12$个首字母组成了一个拉丁字母表，这些单词被标记为$1$到$n$。在每个单词内各个相邻的字母是不同的。对于第$i$个单词，$Monocarp$有一个整数$c_i$表示他使用这个词的频率。 $Monocarp$想要设计一个可以让他轻易输入一些单词的键盘。这个键盘可以表示这$12$个首字母组成的拉丁字母表,且所有字母只出现一次。 一个单词是否能被轻松的表示出来，取决于单词内每一对相邻的字母是否也一样在键盘中相邻。一个键盘的价值是所有能被它表示出来的单词$i$的频率$c_i$的总和。 请你帮助$Monocarp$设计一个价值尽可能高的键盘。 ## 输入格式 第一行一个整数$n(1≤n≤1000)$——单词的数量 之后输入$n$行，第$i$行包括一个整数$c_i(1≤c_i≤10^5)$和一个字符串$s_i(2≤|s_i|≤2000)$表示第$i$个单词。所有在$s_i$的字母是拉丁字母表内的一个单词的首字母且它们是小写字母。保证对于任意一个$j∈[1,∣s_i​ ∣−1]$，$s_i$的第$j$个字母和第$j+1$个字母不同。 输入数据保证$\sum_{i=1}^n ∣s_i∣≤2000$。 ## 输出 输出一串，12个拉丁单词的首字母，每个字母只能输出一个。表示最大价值状态下的键盘。如果有多个答案，只用输出任意一种即可。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

3
7 abacaba
10 cba
4 db

输出样例 #1

hjkildbacefg

输入样例 #2

1
100 abca

输出样例 #2

abcdefghijkl

**题目大意**：

Monocarp有一个包含n个单词的字典，这些单词由12个拉丁字母表的首字母组成，单词从1到n编号。每个单词内部的相邻字母各不相同。对于第i个单词，Monocarp有一个整数\( c_i \)表示他使用该词的频率。

Monocarp想要设计一个键盘，使得他能轻松输入一些单词。这个键盘可以表示这12个首字母组成的拉丁字母表，且每个字母只出现一次。

一个单词是否能被轻松地输入，取决于单词内每一对相邻字母是否在键盘中也是相邻的。键盘的价值是所有能被它轻松输入的单词\( i \)的频率\( c_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 \)的字母是拉丁字母表内的一个单词的首字母且它们是小写字母。保证对于任意一个\( j \in [1, |s_i| - 1] \)，\( s_i \)的第\( j \)个字母和第\( j+1 \)个字母不同。
- 输入数据保证\( \sum_{i=1}^n |s_i| \le 2000 \)。

**输出**：

输出一串，12个拉丁单词的首字母，每个字母只能输出一个。表示最大价值状态下的键盘。如果有多个答案，只用输出任意一种即可。

**输入输出样例**：

**输入样例 #1**：
```
3
7 abacaba
10 cba
4 db
```
**输出样例 #1**：
```
hjkildbacefg
```

**输入样例 #2**：
```
1
100 abca
```
**输出样例 #2**：
```
abcdefghijkl
```**题目大意**： Monocarp有一个包含n个单词的字典，这些单词由12个拉丁字母表的首字母组成，单词从1到n编号。每个单词内部的相邻字母各不相同。对于第i个单词，Monocarp有一个整数\( c_i \)表示他使用该词的频率。 Monocarp想要设计一个键盘，使得他能轻松输入一些单词。这个键盘可以表示这12个首字母组成的拉丁字母表，且每个字母只出现一次。 一个单词是否能被轻松地输入，取决于单词内每一对相邻字母是否在键盘中也是相邻的。键盘的价值是所有能被它轻松输入的单词\( i \)的频率\( c_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 \)的字母是拉丁字母表内的一个单词的首字母且它们是小写字母。保证对于任意一个\( j \in [1, |s_i| - 1] \)，\( s_i \)的第\( j \)个字母和第\( j+1 \)个字母不同。 - 输入数据保证\( \sum_{i=1}^n |s_i| \le 2000 \)。 **输出**： 输出一串，12个拉丁单词的首字母，每个字母只能输出一个。表示最大价值状态下的键盘。如果有多个答案，只用输出任意一种即可。 **输入输出样例**： **输入样例 #1**： ``` 3 7 abacaba 10 cba 4 db ``` **输出样例 #1**： ``` hjkildbacefg ``` **输入样例 #2**： ``` 1 100 abca ``` **输出样例 #2**： ``` abcdefghijkl ```