가격 평가

어느 날 다빈치는 작업실에 완성된 그림이 쌓여 있어 돌아다니기 불편해졌다. 그래서 그는 가장 아끼는 제자 프란체스코 멜치를 보내 그중 한 작품을 팔게 했다. 다빈치는 가격을 아주 단순한 방식으로 정했다. 먼저 가능한 모든 속성(화풍, 주제, 계절, 날씨 등)에 가격을 매기고, 팔 작품이 가진 여러 속성을 짚은 다음, 그 속성들의 가격을 모두 더해 작품의 가격으로 삼았다. 그런 다음 다빈치는 프란체스코 멜치에게 가격표와 그 작품의 속성을 알려주었다.

프란체스코가 작품을 팔러 나섰을 때, 그는 작품의 일부 속성을 잊어버렸지만 각 속성의 가격은 아주 잘 기억하고 있었다. 그가 기억하는 정보만으로 이 작품의 가격은 최소 얼마, 최대 얼마가 될 수 있을까?

첫 줄에는 입력 데이터 세트의 개수 1 ≤ K ≤ 10이 주어진다. 이어서 다음과 같은 형식의 데이터 세트 K개가 주어진다.

데이터 세트의 첫 줄에는 두 정수 n, m이 주어진다. 1 ≤ m ≤ n ≤ 100이며, n은 가능한 모든 속성의 개수, m은 팔 작품이 가진 속성의 개수다. 이어서 n개의 줄에 각각 문자열 si와 정수 0 ≤ ci ≤ 10000이 공백으로 구분되어 주어진다. si는 i번째 속성의 이름이고 ci는 그 속성에 매겨진 가격이다. si는 길이가 최대 80인 비어 있지 않은 소문자 문자열이다. 모든 si는 서로 다르지만, ci는 같을 수도 있다.

다음 줄에는 이 작품이 가진 속성 m개가 문자열 pj로 공백을 사이에 두고 주어진다. pj가 ?이면 알 수 없는 속성이고, 그렇지 않으면 pj는 속성 si 중 하나다. 아는 속성이 두 번 나오는 경우는 없다.

각 데이터 세트마다 먼저 “Data Set x:”를 한 줄에 출력한다. x는 데이터 세트의 번호다.

그다음 한 줄에 작품 가격의 최솟값과 최댓값을 출력한다.

각 데이터 세트 뒤에는 빈 줄을 하나 출력한다.