카지노
시간 제한2초메모리 제한1024 MB
색깔 있는 칩이 한 줄로 놓여 있고 공지된 색 패턴이 주어질 때, 공지된 연속 패턴을 반복해 제거하면서 얻는 칩 가격의 최댓값을 구합니다.
문제
새로 문을 연 카지노가 독특한 게임을 선보였다. 게임을 시작할 때 딜러는 여러 색깔의 칩을 한 줄로 늘어놓고, 플레이어가 가져갈 수 있는 연속된 칩의 나열을 미리 발표한다. 플레이어는 발표된 나열 중 하나를 가져가고, 딜러가 남은 칩을 당겨 빈틈을 없앤다. 그다음 플레이어는 다시 발표된 나열 중 하나를 가져가고, 이 과정을 반복한다. 플레이어가 칩을 가져갈 수 있는 동안 게임은 계속된다. 예를 들어 칩 줄이 rrrgggbbb이고 딜러가 rg와 gb를 발표했다고 하자. 플레이어는 왼쪽에서 세 번째와 네 번째에 있는 rg를 가져갈 수 있다. 그러면 칩이 당겨져 줄은 rrggbbb가 된다. rg를 두 번 더 가져가면 bbb만 남고, 더 가져갈 것이 없으므로 게임이 끝난다. 플레이어는 두 번째와 세 번째 차례에 gb를 가져갈 수도 있는데, 이때는 rrb가 남는다. 같은 방식으로 rrr이나 rbb가 남도록 할 수도 있다. 게임이 끝나면 플레이어는 얻은 칩을 돈으로 바꾼다. 칩의 가격은 색깔에 따라 정해진다.
입력
첫 줄에 칩 색깔의 개수 K (1 이상 26 이하)가 주어진다. 이어지는 K개 줄마다 색깔을 나타내는 소문자 라틴 문자로 시작하고, 공백 뒤에 그 색깔 칩의 가격 Xi (1 이상 150 이하)가 정수로 주어진다. K+2번째 줄에는 게임 시작 때 탁자 위에 놓인 칩 줄이 소문자 라틴 문자 L개로 주어진다 (1 이상 150 이하). 다음 줄에는 딜러가 발표한 나열의 개수 N (1 이상 150 이하)이 주어진다. 그다음 N개 줄에 이 나열들이 주어진다. N개 줄의 길이 합은 150을 넘지 않으며, 모든 나열은 비어 있지 않다.
출력
플레이어가 얻을 수 있는 금액의 최댓값을 정수 하나로 출력한다.