[Solution] Keyboard Design solution codeforces

Keyboard Design solution codeforces – Monocarp has a dictionary of 𝑛n words, consisting of 1212 first letters of the Latin alphabet. The words are numbered from 11 to 𝑛n. In every pair of adjacent characters in each word, the characters are different. For every word 𝑖i, Monocarp also has an integer 𝑐𝑖ci denoting how often he uses this word.

Table of Contents

[Solution] Keyboard Design solution codeforces

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 1212 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 𝑐𝑖ci over all words 𝑖i that can be typed easily with it.

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

Input

The first line contains one integer 𝑛n (1𝑛10001≤n≤1000) — the number of words.

Then, 𝑛n lines follow. The 𝑖i-th of them contains an integer 𝑐𝑖ci (1𝑐𝑖1051≤ci≤105) and a string 𝑠𝑖si (2|𝑠𝑖|20002≤|si|≤2000) denoting the 𝑖i-th word. Each character of 𝑠𝑖si is one of 1212 first letters of Latin alphabet, in lowercase. For every 𝑗[1,|𝑠𝑖|1]j∈[1,|si|−1], the 𝑗j-th character of 𝑠𝑖si is different from the (𝑗+1)(j+1)-th one.

Additional constraint on the input: 𝑖=1𝑛|𝑠𝑖|2000∑i=1n|si|≤2000.

[Solution] Keyboard Design solution codeforces

Print a sequence of 1212 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.

Examples
input

Copy
3
7 abacaba
10 cba
4 db
output

Copy
hjkildbacefg

[Solution] Keyboard Design solution codeforces

Copy
1
100 abca
output

Copy
abcdefghijkl

 

For Solution

“Click Here”

Leave a Comment