提示: 欢迎访问OurACM平台。
Problem 2162 largeCommon

Accept: 14    Submit: 73
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

给你2个字符串s1,s2。同时给n个不同字符串和每个的价值value。找出一个s1与s2的公共子序列价值最大,价值等于子序列中包含的子串的value的总和(仅计算给出的n)。

Input

对于每组数据,先输入两个字符串s1,s2(1=<|s1|,|s2|<=100),然后一个整数n,然后输入n个字符串和价值value(-1000<=value<=1000)。并且n个串的长度总和小于等于100.所有字符的为小写。

Output

输出最大的价值

Sample Input

ababc ababc 2 ababc -100 ab 10

Sample Output

20

Submit  Back  Status  Discuss