꿍의 여친 만들기

꿍은 좋아하는 여학생 앞에 나서기 전에 그녀가 원하는 조건부터 맞추기로 했다. 알아보니 그녀의 취향은 여러 조합 중 하나만 만족하면 되는 형태였다. 예를 들어 똑똑하고(intelligent) 세련되고(cultivated) 옷을 잘 입는(welldressed) 남자, 오토바이가 있고(motorcycleowner) 살짝 무뚝뚝한(rude) 남자, 아니면 그냥 부자(rich)면 된다.

조건 하나를 만족시키는 데 걸리는 시간은 조건마다 정해져 있다. 꿍은 여러 조건을 동시에 진행할 수 있으므로, 한 조합에 필요한 시간은 그 조합에 들어 있는 조건의 시간 중 가장 큰 값이다. 조합이 여러 개면 그중 하나만 만족시키면 된다.

조건별 시간과 조합 목록이 주어질 때, 그녀를 만족시키는 데 걸리는 최소 시간을 구하여라.

첫째 줄에 테스트케이스의 개수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트케이스는 두 줄로 이루어진다.

첫째 줄에는 조건의 이름과 시간이 쉼표(,)로 구분되어 주어진다. 각 항목은 이름, 콜론(:), 시간 순서로 붙어 있다. 이름은 소문자 a부터 z까지로만 이루어지고 길이는 1 이상 20 이하이며, 시간은 0 이상 1000 이하의 정수다. 한 테스트케이스의 조건은 20개를 넘지 않고 이름은 서로 다르다.

둘째 줄에는 그녀가 만족하는 조합 목록이 주어진다. 조합끼리는 세로줄(|)로, 한 조합 안의 조건끼리는 앰퍼샌드(&)로 구분된다. 조합은 10개를 넘지 않고, 각 조합에는 조건이 하나 이상 들어 있으며 같은 조건이 두 번 나오지 않는다. 조합에 쓰인 이름은 모두 첫째 줄에 정의되어 있다. 입력에는 공백이 없다.

각 테스트케이스마다 그녀를 만족시키는 데 걸리는 최소 시간을 한 줄에 하나씩 출력한다.

둘째 줄은 (조합 1) | (조합 2) | (조합 3) 형태로 읽으면 된다.