시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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 si and an integer 0 ≤ ci ≤ 10000 separated by space, where si is the name of the i-th property and ci is the price assigned to it. si is a non-empty string consisting of at most 80 lowercase letters. All si’s are unique, but ci’s are not necessarily unique.

Next is a line containing m strings pj separated by space: the properties this artwork has. If pj is ?, then it is an unknown property, otherwise pj would be one of the properties si. 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.

예제 입력 1

2
5 3
beautiful 8
oilpainting 3
portrait 3
gorgeous 5
spring 4
beautiful ? oilpainting
4 4
landscape 6
snowy 7
winter 5
earlywork 3
? winter ? ?

예제 출력 1

Data Set 1:
14 16

Data Set 2:
21 21