#102309. [BZOJ 2309] [Ctsc2011]字符串重排

对于两个字符串 和 ，定义其最长公共前缀长度 如下：

给定 个由小写字母组成的两两不同的非空字符串 ，对于一个 到 的排列 ，定义 的价值 如下：

我们设能够产生最大价值的排列为 。此外，还有 个附加任务。对于第 个任务，给定两个 到 之间的不同的整数 和 。对于排列 ，若 在满足 的前提条件之下，同时满足第 个字符串 恰好排在第 个字符串 之前，即 ，其中 表示字符串 在排列中的位置，则排列 还将获得 的奖励。所有任务的奖励之和称之为总任务奖励。我们设能够使得总任务奖励最大的排列为 。试求：

1. ，即可能产生的最大价值；
2. ，在保证最大价值前提下，可以使总任务奖励最大的排列。

第一行包含两个整数 和 ，表示字符串和附加任务的数量，中 间用一个空格隔开。
接下来 行，描述字符串，其中第 行包含一个字符串 。
接下来 行，描述附加任务，其中第 行包含两个整数 和 ，中间用一个空格隔开。

输出是第一行最大价值；
第二行若干个数，每两个数之间用一个空格隔开，这一行第一个数表示满足附加任务的数量 ，接下来 个数为这些任务的序号，序号从 开始，按从小到大的顺序输出；
第三行包含 个用一个空格隔开的正整数，表示一个 到 的排列 。

样例输入 #1

4 6
a
b
abc
bc
1 2
1 3
3 1
4 2
2 4
2 4

样例输出 #1

2
4 1 3 5 6
3 1 2 4

对于 的数据，，，每个字符串的长度不超过 ；
对于 的数据，，，每个字符串的长度不超过 ；
对于 的数据，，每个字符串的长度不超过 ；
对于 的数据，任意字符串不为其他任何一个字符串的前缀；
对于 的数据，，，每个字符串的长度不超过 ，所有字符串的长度和不超过 。

评分方式

对于一个测试点：

• 如果输出文件的第一行正确可以得到 分；
• 如果输出文件的第二行正确可以得到 分；
• 如果输出文件的第三行正确可以得到 分；
• 如果输出文件的三行都正确则可以得到 分。
• 对于第三问中的排列，如果存在多个解， 则输出任意一个解均可得分。 若某问无法完成，也请按照格式输出，以避免测评失败。

鸣谢 wjbzbmr