시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 15 0 0 0.000%

문제

선영이는 테트리스 같은 게임을 하고 있다.

게임은 비어있는 세 열에서 시작한다. 게임이 진행되는 동안 글자가 하나씩 화면의 가장 위에 보여진다. 글자가 보여지면, 선영이는 세 열중 하나를 선택한다. 선택한 열이 비어있다면, 그 열의 가장 아래에 글자를 놓고, 비어있지 않다면, 그 열의 가장 위에 있는 단어의 위에 글자를 놓는다.

게임이 끝난 후에 선영이가 얻은 점수는 각 열의 점수의 합이다. 각 열의 점수는 다음과 같이 계산할 수 있다.

먼저, 동일한 단어로 이루어진 그룹을 모두 찾는다.

예를 들어, 어떤 열의 글자가 아래 그림과 같다고 하자.

위의 그림에는 총 4개의 그룹이 있다. 그 다음, 각 그룹의 크기(포함되어 있는 글자의 개수)에 따라서 점수를 계산하면 된다.

예를 들어, 크기가 1인 그룹은 3점, 2인 그룹은 7점, 3인 그룹은 5점이라고 한다면, 위의 그림은 5+3+5+7=20점이 된다.

각 그룹의 점수와 화면의 가장 위에 보여지는 글자가 순서대로 주어진다. 이 때, 선영이가 테트리스 같은 게임에서 얻을 수 있는 가장 높은 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 정수 B1, B2, B3, B4, B5가 주어진다. i=1,2,3,4인 경우에 Bi는 글자 i개로 이루어진 그룹의 점수이고, B5는 글자 5개 또는 그 이상으로 이루어진 그룹의 점수이다. 이 다섯 정수는 100보다 작거나 같다.

둘째 줄에는 화면에 보여지는 글자의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

셋째 줄에는 화면에 보여지는 글자 N개가 순서대로 주어진다. 글자는 알파벳 대문자이다.

출력

첫째 줄에 선영이가 얻을 수 있는 가장 높은 점수를 출력한다.

예제 입력

3 3 10 3 3
17
AAABBCCCAAACBAAAB

예제 출력

56

힌트

예제의 경우에 아래와 같이 쌓으면 가장 높은 점수를 얻을 수 있다.

|   | 
|A  | 
|A  | 
|A  | 
|B  | 
|A  | 
|A  | 
|A  | 
|C  | 
|ABC| 
|ABC| 
|ABC| 
+---+