F. Дизайн клавиатуры
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть словарь из $$$n$$$ слов, состоящих из первых $$$12$$$ букв латинского алфавита. Слова пронумерованы от $$$1$$$ до $$$n$$$. Во всех парах соседних букв в слове буквы различны. Каждому слову $$$i$$$ Монокарп сопоставил целое число $$$c_i$$$ — как часто он использует это слово.

Монокарп хочет выбрать такой дизайн клавиатуры, чтобы он помог ему проще печатать некоторые слова. Клавиатуру можно описать, как последовательность из $$$12$$$ первых букв латинского алфавита, где каждая буква от a до l встречается ровно один раз.

Слово можно легко напечатать на клавиатуре, если для каждой пары соседних символов в слове эти символы на клавиатуре тоже соседние. Оптимальность клавиатуры — это сумма $$$c_i$$$ по всем словам $$$i$$$, которые могут быть легко на ней напечатаны.

Помогите Монокарпу создать дизайн клавиатуры с максимальной оптимальностью.

Входные данные

В первой строке записано одно целое число $$$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]$$$, $$$j$$$-й символ в $$$s_i$$$ отличается от $$$(j+1)$$$-го.

Дополнительное ограничение на входные данные: $$$\sum \limits_{i=1}^{n} |s_i| \le 2000$$$.

Выходные данные

Выведите последовательность из $$$12$$$ первых букв латинского алфавита, где каждая буква от a до l встречается ровно один раз, определяющую оптимальную клавиатуру. Если ответов несколько, выведите любой из них.

Примеры
Входные данные
3
7 abacaba
10 cba
4 db
Выходные данные
hjkildbacefg
Входные данные
1
100 abca
Выходные данные
abcdefghijkl