kockice

문제

Little Luka is playing an interesting tetris-like game. 

In the beginning of the game, there are three empty columns on the screen. During the game, letters appear on the top of the screen. When a letter appears, Luka chooses one of the columns and puts this letter on top of the topmost letter in that column, or on the bottom if that column is empty. 

When the game is over, we define the total number of points that Luka gets as sum of the points for each column. The number of points for a column is calculated in the following way: we first find groups of identical consecutive letters (borders between two groups are between different letters). 

For example, if the letters in some column are: 

A
A
A
B
C
C
C
A
A

then this column consists of 4 groups. Now, for each of the groups, we get some number of points that depends only on the number of letters in that group. 

For example, if we get 3 points for the groups with size 1, 7 points for the groups with size 2, and 5 points for the groups with size 3, then the number of points for the example column would be 5+3+5+7=20. 

Write a program that, given a sequence of letters and the assignment of scores to group sizes, finds the maximum number of points that Luka can get in this game.

입력

The first line of input contains five integers B₁, B₂, B₃, B₄, and B₅. For i=1,2,3,4 the number B_i is the number of points for groups consisting of i letters and the number B₅ is the number of points for groups of 5 or more letters. Each of these 5 numbers will be less than or equal to 100. 

The second line contains an integer N, 1 ≤ N ≤ 1000 – the number of letters appearing. 

The third line contains a sequence of N uppercase letters of the English alphabet ('A'-'Z'), in the order in which they appear on the top of the screen during the game. 

출력

The first and only line of output should contain a single integer – the maximum number of points from the task description. 

5 5 5 5 5
9
ABCABCABC

45

1 5 1 1 1
9
ABCABCABC

18

3 3 10 3 3
17
AAABBCCCAAACBAAAB

56