Original problem statements can be found here: in Polish and in English.

Aliens attack! Run for your lives!

... or not, it's only a video game. And even then, although alien spaceships are flying straight for the Earth, it's not terribly important to destroy them all. Gregory the Gamer only wants that sweet high score.

To be more precise, there are n enemy spaceships, flying in a row. Every spaceship is of one of three colours. Our own spaceship is flying opposite of those, from left to right, and can destroy any of them. Destroying a spaceship of colour i is worth p_i points. If you destroy more than one spaceship of the same color in a row, you get more points - second spaceship in sequence is worth 2p_i points, for the third one you get 3p_i and so on. The maximum number of points you can get for one spaceship is limited by M - if the previous rule dictates more than that, you get exactly M points instead.

What is the highest score Gregory can get?

Input

The first line contains a single integer t, denoting number of testcases. Then, testcases follow.

The first line of a testcase contains two integers n, M - number of spaceships and points limit for one spaceship ( 1 <= n <= 10⁵, 1 <= M <= 100 ).

In the next line there are three integers 1 <= p_A, p_B, p_C <= M - point values for destroying spaceships of different colours.

In the last line there is a string of length n - description of subsequent spaceships. Every character is one of the following: A, B, C. Different characters correspond to different colours.

Output

For every testcase you should output one integer - highest score you can get.

Example

Input:

2
7 5
1 1 5
AAACAAA
6 10
1 1 10
ABABAB

Output:

20
7

Explanation

In the first testcase we destroy all six spaceships of colour A, and we get 1+2+3+4+5+5 = 20 points. If we destroyed all of them instead, we'd get (1+2+3)+5+(1+2+3) = 17 points.

In the second testcase we can first destroy all spaceships of colour A, and then the last spaceship of colour B, which will give us (1+2+3)+1 = 7.