노래
시간 제한1초메모리 제한256 MB
26 by 26 쌍 점수표가 주어질 때 C로 시작하는 L개 음표 노래 중 인접한 쌍 점수 합이 가장 큰 값을 구합니다.
문제
토끼용 악기에는 A부터 Z까지 영어 대문자로 적는 음 26개가 있다. 이 문자를 이어 붙이면 토끼 노래가 되고, 문자 하나는 그 음을 한 박자 연주한다는 뜻이다. 노래의 길이는 문자의 개수다. 예를 들어 AASDFG는 길이가 6인 노래이고, 1박자에 A, 2박자에 A, 3박자에 S, 4박자에 D, 5박자에 F, 6박자에 G를 연주한다.
토끼 심리학자는 번째 박자의 음이 주는 행복도가 번째 박자의 음과 번째 박자의 음이 이루는 짝으로 정해진다는 사실을 알아냈다. 이 값은 음 행복도 표에 적혀 있고, 표는 토끼마다 다르다. 표의 행은 번째 박자의 음, 열은 번째 박자의 음을 뜻하며 둘 다 A부터 Z 순서다. 행이 , 열이 인 칸의 값을 라고 하자. 1박자의 음은 행복도를 주지 않으므로 노래 AASDFG의 행복도는 이다.
음 행복도 표와 노래의 첫 음, 노래의 길이가 주어진다. 이 조건을 지키는 노래가 줄 수 있는 가장 큰 행복도를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다 (). 각 테스트 케이스는 다음과 같이 이루어진다.
- 음 행복도 표가 26줄에 걸쳐 주어진다. 각 줄에는 행복도 26개가 공백으로 구분되어 주어진다 (). 번째 줄의 번째 값은 번째 음 다음에 번째 음을 연주할 때 얻는 행복도이고, 음의 순서는 A부터 Z까지다.
- 다음 줄에 질문의 개수 이 주어진다 ().
- 다음 개의 줄에 노래의 첫 음을 나타내는 영어 대문자 와 노래의 길이 이 공백으로 구분되어 주어진다 ().
출력
각 질문마다 첫 음이 이고 길이가 인 노래로 얻을 수 있는 가장 큰 행복도를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.