#5575. 盗墓 2

盗墓 2

题目背景

小吴、小张两个摸金校尉和你偶然的机会发现了一座未被开发的古墓。进入古墓后,肉眼可见的辉煌装饰、雕刻、壁画,让你们来了兴致,一拍即合决定深入调查,挖掘古墓深处的财宝。

走到走廊的尽头,你们发现了一个巨大的石门,无论如何用力都无法打开,但石门上似乎有一些机关,破解机关说不定可以打开石门!

题目描述

机关上有一个长度为 66 的凹槽,同时地上还有 nn 个长方形的木块,每个木块的长度参差不齐,并且上面还有一串英文字母,木块前 33 个字母还能通过旋转拆卸下来,长度还刚好为 33,这让你们意识到,22 个小木块就能刚好填满凹槽。

同时机关上形似“大”的图案,让你们联想到可能是需要用任意 22 个小木块拼接出最大的组合,英文字符串的“最大”肯定是字典序最大了!

你们决定实践起来,但木块实在太多了,操作起来有点麻烦,于是决定由你来编写一个程序,找出拼接出来最大的木块来填满凹槽,破解机关。

输入格式

第一行输入一个整数 n(2n6000)n(2 \leq n \leq 6000),表示木块的数量。

接下来 nn 行,每行一个字符串,表示每个木块上的字母内容,只包含小写字母,并且字符串的长度在 3103 \sim 10 的范围内。

输出格式

输出一个长度为 66 的字符串,表示用 22 个长度为 33 的小木块所能拼接出的字典序最大的组合。

输入输出样例 #1

输入 #1

3
abcdefghij
xyzkkxxxkx
xbcfzibaoejab

输出 #1

xyzxbc

说明/提示

数据约束:

对于 50%50\% 的数据 2n1002 \leq n \leq 100

对于 80%80\% 的数据 2n10002 \leq n \leq 1000

对于 100%100\% 的数据 2n60002 \leq n \leq 6000