이름 망치기
시간 제한2초메모리 제한512 MB
모음과 자음 개수별 발음 시간 표가 주어질 때, 각 학생 이름의 발음 시간을 모두 더해 전체 시간을 구한다.
문제
모두의 이름과 성을 알아냈으니, 이제 모두가 무대를 걸어 나가 친구와 가족의 환호를 받으며 학위를 받고, 자기 이름이 발음되거나 망가지는 소리를 들을 차례이다. 하지만 수백, 수천 개의 이름을, 그것도 수십 개국의, 일부는 아주 긴 이름을 발음해야 하는 불쌍한 관계자들에게는 좀 측은한 마음이 들 수밖에 없다. 이름을 제대로 발음하는 데 시간이 걸리면 졸업식 전체가 지연된다. 이 문제에서는 그 지연이 얼마나 되는지 계산한다.
이름에 들어 있는 모음(‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘y’. ‘y’는 항상 모음으로만 취급하고 자음으로는 취급하지 않는다)의 개수와 자음의 개수에 따라 이름을 정확히 발음하는 데 걸리는 시간을 알려 주는 표가 주어진다. 그리고 졸업생마다 이름이 주어진다. 졸업식 전체의 길이를 출력하시오.
입력
첫 줄에는 입력 데이터 세트의 개수 1 ≤ K ≤ 100이 주어진다. 이어서 K개의 데이터 세트가 다음 형식으로 주어진다.
각 데이터 세트의 첫 줄에는 두 정수 0 ≤ L ≤ 30, 0 ≤ n ≤ 100, 000이 주어진다. 여기서 L은 어떤 이름에든 들어 있는 모음 또는 자음 개수의 최댓값(둘 중 큰 쪽)이고, n은 입장하는 학생 수이다.2 이어서 L + 1개의 줄이 주어지며, 각 줄에는 L + 1개의 정수가 있다. i번째 행의 j번째 항목은 정수 0 ≤ pi,j ≤ 100으로, 모음 i개와 자음 j개를 가진 이름을 발음하는 데 걸리는 시간(초)을 나타낸다. 여기서 0 ≤ i, j ≤ L이다.
이어서 n개의 줄이 주어지며, 각 줄에는 길이가 2L 이하인 문자열이 있다. 이 문자열은 소문자로만 이루어져 있고, 학생의 이름이다. 이름에는 모음이 L개 이하, 자음이 L개 이하로 들어 있다.
2n을 100,000까지 허용하는 게 궁금하다면, 요즘 우리 졸업식을 본 적이 있는가?!?
출력
각 데이터 세트마다 먼저 “Data Set x:”를 한 줄에 단독으로 출력한다. 여기서 x는 데이터 세트의 번호이다.
그다음 줄에 졸업식 전체의 길이를 초 단위로 출력한다.
각 데이터 세트 뒤에는 빈 줄을 출력한다.