## SPA - Spaceships in Space

*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^{5}, 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.

hide comments

:D:
2019-12-16 00:20:48
Great problem. Simple and clear description, but very interesting to implement and challenging to optimize. I will probably try to push my time down further. |

Added by: | Piotr Jagiełło |

Date: | 2018-03-30 |

Time limit: | 1s-5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | PIZZA 2018 qualifying round |