OI题库

问题描述：

一位信使来到一个村落送信，不幸的事由于下雨他的信件信封上的地址都模糊不清，只剩下连续的一小部分可以辨认。村落中共有m户居民，每户村民的地址可以用一个只含有小写字母的字符串表示，第i户村民的地址为Ai;信使需要投送n封信件，第j封信件信封上可以辨认的部分地址记作Bj，若Bj为Ai的子串，则第i户家庭可能为第j封信件的收件人。最坏情况下，信使可能需要走遍一封信件的所有可能收件人才能将信件投送出去。

一些信件还附带有包裹，因此每封信件都有一个重量值Wi，信使从一户村民X移动到另一户村民Y的代价为到达Y时身上所携带的信件重量只和。

信使不想走太长的路，因此他希望每户人家只经过一次，即所走的路径为一条链，在这个前提下他请你帮他设计一条路线，使得在最坏情况下投送完所有信件所花费的代价最小。

输入格式：

输入数据共n+m+1行：

第1行为两个整数m、n，表示村落中共有m户村民，信使需要投送n封信件。

第2行到第m+1行每行为一个字符串，表示第每户村民的地址。

第m+2行到第n+m+1行每行有一个整数和一个字符串，表示每封信件的重量以及可辨认出的地址。

输出格式：

输出数据仅有1行，为在最坏情况下的最小代价。

输入样例(postmana.in)：

3 3

a

b

ab

1 a

3 b

2 ab

输出样例：

5

样例解释：
信使的路线为ab->b->a，最坏情况下在ab投送出第三封信，在b投送出第二封信，在a投送出第一封信。ab->b的代价为1+3=4，b->a的代价为1，总代价和为5。

数据规模：

10%的数据满足1≤m,n≤15

30%的数据满足1≤m,n≤100

100%的数据满足1≤m,n≤5000, 0≤Wi≤100, 每个信件的字符串的长度Ln≤300，每户村民的地址字符串长度Lm≤2000。

数据保证每封信件都至少有一个可能的收信人，且每户村民都至少成为一封信件的可能收信人。