18009번 - Price Evaluation 다국어

One day, da Vinci found his workspace piled with completed paintings, making it difficult to move around. He then sent out his favorite student, Francesco Melzi, to sell one of these artworks. Da Vinci decided to determine the price in a quite simple way: he firstly assigned a price to each possible property (style, subject, season, weather, etc.), then named several properties of the painting to sell, and set the price of it to be the sum of prices of these properties. After that, da Vinci told Francesco Melzi the assignment of prices and the properties of that painting.

When Francesco set out to sell the artwork, he forgot some of its properties but memorized the price of each property very well. He wondered according to the information he remembered, what would the painting’s minimum and maximum possible price be?

The first line contains a number 1 ≤ K ≤ 10, which is the number of input data sets in the file. This is followed by K data sets of the following form:

The first line of a data set contains two integers n, m with 1 ≤ m ≤ n ≤ 100: n is the number of all possible properties, and m is the number of properties of the artwork to sell. This is followed by n lines, each with a string s_i and an integer 0 ≤ c_i ≤ 10000 separated by space, where s_i is the name of the i-th property and c_i is the price assigned to it. s_i is a non-empty string consisting of at most 80 lowercase letters. All s_i’s are unique, but c_i’s are not necessarily unique.

Next is a line containing m strings p_j separated by space: the properties this artwork has. If p_j is ?, then it is an unknown property, otherwise p_j would be one of the properties s_i. No known property will appear twice.

For each data set, first output “Data Set x:” on a line by itself, where x is its number.

Then, output the minimum and maximum possible price of the artwork on a single line.

Each data set should be followed by a blank line.