Keyboard Design
Contest: Educational Codeforces Round 136 (Rated for Div. 2)
Difficulty rating: 2600
Tags: bitmasks, data structures, dp, string suffix structures, strings

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Example input:
3
7 abacaba
10 cba
4 db

Example output:
hjkildbacefg

Example input:
1
100 abca

Example output:
abcdefghijkl

Editorial:
For each word, let's consider a graph on $$$12$$$ vertices where the $$$i$$$-th and the $$$j$$$-th vertices are connected by an edge iff the $$$i$$$-th character of the alphabet is adjacent to the $$$j$$$-th character of the alphabet in this string. Obviously, this graph is connected (except for the isolated vertices). If there is a vertex of degree $$$3$$$ or more in this graph, or if there is a cycle in this graph, it is impossible to design a keyboard to type the word easily: in the first case, the letter represented by that vertex must have at least three neighbors on the keyboard, but can have only at most two; in the second case, the keyboard must be cyclic (and it is not). So, the word can be typed easily only if the graph representing it consists of one path and several isolated vertices.
Let's write the letters along the path we constructed for the word in a single string. For example, for the word abacabacd, we get edges ab, ac and cd in the graph, so the letters along the path are either dcab or bacd (and, obviously, one can be obtained from the other by reversing the string). Let $$$f(s)$$$ and $$$f'(s)$$$ be the two strings we obtain from the word $$$s$$$ using this method. Now, we claim that the word $$$s$$$ can be typed easily if and only if one of these two strings ($$$f(s)$$$ and $$$f'(s)$$$) is a substring of the keyboard — this would mean that every pair of letters that should be on adjacent positions are actually on adjacent positions.
Okay, now we construct $$$f(s_i)$$$ and $$$f'(s_i)$$$ for each word, and our goal is to find the permutation of the first $$$12$$$ characters of Latin alphabet such that the sum of $$$c_i$$$ over all words having either $$$f(s_i)$$$ or $$$f'(s_i)$$$ as a substring is the maximum possible. There are two key observations that allow us to solve this problem:
• $$$f(s_i)$$$ and $$$f'(s_i)$$$ cannot be the substrings of the same keyboard (the proof is simple: if $$$f(s_i)$$$ is a substring, its first character must be before its second character; and if $$$f'(s_i)$$$ is a substring, its second-to-last character (which is the second character of $$$f(s_i)$$$) must be before its last character (which is the first character of $$$f(s_i)$$$);
• neither $$$f(s_i)$$$ nor $$$f'(s_i)$$$ can appear in the keyboard twice (it's obvious since the keyboard is a permutation).
So, we can reformulate the problem as follows: let $$$c_i$$$ be the cost of the string $$$f(s_i)$$$ and the cost of the string $$$f'(s_i)$$$ as well; find the permutation of the first $$$12$$$ characters of the Latin alphabet so that its cost (which is the sum of costs of its substrings) is the maximum possible. To solve this problem, we can store the strings in an Aho-Corasick automaton, and for every state of the automaton, precalculate the total cost of all string ending in this state (that is, the cost of this state and all states reachable from it via the suffix links). Then run a dynamic programming of the form $$$dp_{mask,v}$$$ — the maximum possible cost of a partial keyboard if we used a $$$mask$$$ of characters and the Aho-Corasick automaton is currently in the state $$$v$$$. This dynamic programming runs in $$$O(2^K \cdot K \cdot A)$$$, where $$$K$$$ is the size of the alphabet ($$$12$$$), and $$$A$$$ is the size of the automaton (up to $$$4000$$$).