패스트 푸드 상금

대전에서 지역 프로그래밍 대회가 열리는 동안, 대전의 패스트 푸드 음식점은 가게를 알리려고 이벤트를 연다. 정해진 음식을 하나 먹을 때마다 스티커를 한 장 주고, 모은 스티커는 상금으로 바꿔 준다.

상금마다 필요한 스티커 종류가 정해져 있다. 그 상금이 요구하는 종류의 스티커를 한 장씩 내면 상금을 받고, 스티커가 남아 있는 한 같은 상금을 여러 번 받을 수 있다. 스티커는 종류마다 많아야 한 상금에만 쓰이므로, 서로 다른 두 상금이 같은 종류의 스티커를 함께 요구하는 일은 없다. 어느 상금에도 쓰이지 않는 스티커도 있다.

대회를 보러 가는 동안 코치는 패스트 푸드 음식점에서만 식사하도록 허락했다. 코치가 모은 스티커로 받을 수 있는 상금 액수의 합은 최대 얼마인가?

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 상금의 가짓수 n (1 ≤ n ≤ 10)과 스티커의 가짓수 m (1 ≤ m ≤ 30)이 주어진다. 스티커 종류에는 1번부터 m번까지 번호가 붙어 있다.

이어지는 n개 줄에는 상금이 한 줄에 하나씩 주어진다. 각 줄에는 그 상금에 필요한 스티커 종류의 수 k (1 ≤ k ≤ m), 필요한 스티커의 번호 k개, 상금의 액수가 차례로 주어진다. 액수는 1,000,000 이하이다.

테스트 케이스의 마지막 줄에는 코치가 가진 1번부터 m번까지 스티커의 개수가 순서대로 주어진다. 개수는 각각 100 이하이다.

각 테스트 케이스마다 받을 수 있는 상금 액수의 최댓값을 한 줄에 하나씩 출력한다.