#P6796. [2019福建夏令营]创造aba

    ID: 6619 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-位运算位集加速背包动态规划线性 DP贪心消除被支配候选字符串Z 算法CF2700

[2019福建夏令营]创造aba

创造 aba(aba)

题目描述

给定 nn 个字符串 S1,S2,…,SnS_1,S_2,\ldots,S_n。从中选择一些字符串,保持它们在输入中的相对顺序并依次拼接,得到一个长度恰好为 KK 的字符串。

选择的下标必须严格递增,因此每个输入位置至多选择一次;选择的字符串不必连续,但每个被选字符串必须完整使用。

在所有能得到的长度为 KK 的字符串中,求字典序最小的一个。

输入格式

第一行两个正整数 n,Kn,K。

接下来 nn 行,每行一个字符串 SiS_i。行末换行不属于字符串;每行其余字符按原样保留。

输出格式

有解时输出一行一个长度为 KK 的字符串,表示字典序最小的答案;若无法得到长度恰为 KK 的字符串,输出 -1。

样例输入

4 18
ditoly
is
vulnerable
invincible

样例输出

ditolyisinvincible

其他样例

原题所提样例 2 文件尚未找到。以下是本版新增的完整无解样例:

2 3
a
b
-1

数据范围与子任务

所有数据满足 1≤n≤30001\le n\le3000,1≤K≤100001\le K\le10000,1≤∣Si∣≤K1\le|S_i|\le K,∑i∣Si∣≤1000000\sum_i|S_i|\le1000000。

本题采用子任务制,只有通过某个子任务的全部测试点才能获得其分数。

子任务 分值 nn 的上界 KK 的上界 ∑i∣Si∣\sum_i\lvert S_i\rvert 的上界
1 1818 100100 500500 5000050000
2 2020 30003000 10001000 3000030000
3 3131 50005000 100000100000
4 1000010000 10000001000000