/ Vijos / 题库 /

学姐吃大虾天妇罗

学姐吃大虾天妇罗

描述

学姐今晚想吃大虾天妇罗, doc便领着她去吃啦. 但是怎么能这样轻易就让馋嘴的学姐吃到大虾天妇罗呢!
doc想起来周五的晚上小岛在 vijos 上办了比赛, 要doc帮忙出数据.
小岛把数据写在了纸上并拍下来给了 doc, 希望doc能帮忙录入到电脑中得到电子版的数据, 这样就可以放到vijos上去接受测试了.
数据由 N 个字符串(只包括小写字母)组成, 并且需要每一个字符串放在独立的一个输入文件中.
doc可以做的事情包括:
(1) 创建一个新的文件(这几乎是瞬间的)
(2) 保存一个文件(这也是瞬间的,且之后不能再被编辑)
(3) 用一个已经保存了的文件来替换当前的新文件,花费时间为P.(新的文件还可以替换后继续编辑)
(4) 删除新文件中任何一个字符,花费时间Q.
(5) 在新文件中任何位置插入一个新的字符,花费时间为T[c], 其中c为插入的新字符.
doc希望学姐可以告诉他, 最短能在多少时间内, 完成所有文件的编辑.
如果学姐能算出来最少用时, doc就会喂她吃一块大虾天妇罗呢! 而且, 高效完成任务后, 周五的晚上就可以出去陪学姐看星星啦 ^_^

格式

输入格式

第一行一个整数T, 表示总的询问次数.
之后有T次询问, 对于每一次询问, 第一行给出两个整数P 和 Q, 第二行给出26个整数, 依次为 T[a],...,T[z]. 满足: 1 <= P , Q , T[] <= 50为整数.
第三行有一个整数N, 表示文件总个数.
之后N行每行有一个由a~z组成的字符串, 依次表示每一个文件中需要录入的字符串.

输出格式

对于每一次询问, 输出一行.
首先输出询问的标号(参见样例输出), 之后输出最少需要花费的时间.
录入的文件顺序没有要求.

样例1

样例输入1

2
10 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
aaab
aaaa
1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
aaab
aaaa

样例输出1

Case #1: 8
Case #2: 7

限制

对于30%的数据: N <= 5, 每一个字符串长度不超过5.
对于60%的数据: 每一个字符串长度不超过10.
对于100%的数据: N <= 50, 每一个字符串长度不超过50. T <= 50.

信息

ID
1899
难度
9
分类
(无)
标签
(无)
递交数
90
已通过
4
通过率
4%
被复制
4
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

NOIP模拟赛 之 周五的夜晚