무기 배분

세오덴 왕은 영토를 노린 습격과 사루만의 위협에 맞서 백성을 헬름 협곡으로 물렸다. 그런데 무기고에 있는 무기가 종류마다 모자라서, 모든 병사에게 가장 잘 다루는 무기를 쥐여 줄 수는 없다. 병참장교는 지금 있는 무기만으로 부대의 전투력이 가장 높아지도록 무기를 나눠 줘야 한다.

병사는 저마다 무기 $N$종류를 가장 잘 다루는 것부터 가장 못 다루는 것까지 차례로 적은 목록이 있다. 어떤 병사가 자기 목록에서 $k$번째 무기를 받으면 미숙련도 합이 $k$만큼 늘어난다. 가장 잘 다루는 무기가 $0$번째다. 목록이 ABCD인 병사는 C를 받으면 $2$, B를 받으면 $1$이 늘어난다. 병사는 모두 무기를 하나씩 받고, 한 무기 종류는 무기고에 있는 개수만큼만 나눠 줄 수 있다. 미숙련도 합의 최솟값을 구하라.

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

각 테스트 케이스의 첫째 줄에는 무기 종류의 수 $N$과 병사의 수 $M$이 주어진다. ($1 \le N \le 26$, $1 \le M \le 200$)

다음 $N$개 줄에는 문자 $C$와 정수 $T$가 주어진다. $C$는 무기 종류를 나타내는 대문자이고, $T$는 무기고에 있는 그 무기의 개수다. ($1 \le T \le 1000$) 문자 $N$개는 서로 다르다.

다음 $M$개 줄에는 병사 한 명의 목록이 한 줄씩 주어진다. 목록은 무기 문자 $N$개를 그 병사가 가장 잘 다루는 순서대로 이어 붙인 문자열이다.

무기고에 있는 무기의 총 개수는 항상 $M$ 이상이므로 모든 병사가 무기를 받는다. 모든 테스트 케이스의 $M$을 더한 값은 $1000$ 이하다.

각 테스트 케이스마다 미숙련도 합의 최솟값을 한 줄에 출력한다.