Match for Bonus
Time Limit: 2 Seconds
Memory Limit: 65536 KB
Roy played a game with his roommates the other day.
His roommates wrote 2 strings of characters, and gave each character a bonus
value. When Roy pinned the positions of one common character in the 2 strings,
the bonus value of that character would be added to Roy's score. However at
the mean time, the 2 characters and those before them in the strings would be
Roy now needs your help, because he wants to know the maximum score he can get.
There are several test cases.
For each test case, the first line contains an integer N.
The following N lines describe a list of N characters and their bonus values.
Then the following 2 lines give the 2 strings.
For each test case, output in one line the best score Roy can get.
Author: SHI, Xiaohan
Source: ZOJ Monthly, September 2003