MVP Diamond (Easy)

Interview

Time limit1sMemory limit512 MB

Summary

Given each month's MVP grade, which depends on the sum paid over the current and previous month, find the maximum total amount paid over all N months.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Implementation, Math
Solved: No attempts yet

Problem

Apart from the input limits, there is no difference between the difficulty versions of this problem.

Sangmin enjoys paying for things in the game Maple Story. Maple Story has 'MVP grades' that grant benefits based on how much money you pay.

There are five MVP grades: Bronze (B), Silver (S), Gold (G), Platinum (P), Diamond (D). Your grade is determined by the current month and the previous month, that is, by the amount you paid over the last 2 months including the current month.

However, to prevent excessive spending, Maple Story has a 'maximum payment limit': in one month you can pay at most the Diamond grade threshold, and payments are possible only in units of ten thousand won.

The MVP grade is calculated and assigned at the end of the month. For example, suppose the grade thresholds are as in the table below, and Sangmin, who started playing in January, paid 300,000 won in January, 200,000 won in February, and 500,000 won in March. Then he is assigned Silver in January (300,000) and February (300,000+200,000=500,000), and Gold in March (200,000+500,000=700,000).

MVP grade (notation)	Grade threshold	Payment over 2 months
Bronze (B)	0 won	0 won ~ 290,000 won
Silver (S)	300,000 won	300,000 won ~ 590,000 won
Gold (G)	600,000 won	600,000 won ~ 890,000 won
Platinum (P)	900,000 won	900,000 won ~ 1,490,000 won
Diamond (D)	1,500,000 won	1,500,000 won or more

Sangmin has spent enormous amounts of cash on the game over the N months since he started playing. He was keeping this fact strictly secret from his girlfriend in particular, because his girlfriend hated that he paid for the game. Then one day a problem arose. His girlfriend got hold of the leaked record of his MVP grades for the past N months!

Sangmin's girlfriend asked you to help her trace back how much he paid.

Sangmin's girlfriend: Tell me the maximum amount Sangmin could have paid for the game.

Nobody knows what will happen between the two of them, but you must write a program for Sangmin's girlfriend.

Input

The first line gives the number of months N that the game was played.

The second line gives the Silver, Gold, Platinum, and Diamond grade thresholds s, g, p, d in that order, in units of ten thousand won. The Bronze grade threshold is 0 won.

The third line gives the MVP grade for each month from the first month to the N-th month of play, using the grade notation. Inputs for which the recorded MVP grades cannot be achieved are not given.

Output

Print the maximum total amount paid, in units of ten thousand won, that could produce the given MVP grades.

Constraints

1 ≤ N ≤ 36

0 < s < g < p < d ≤ 500

An MVP grade Sangmin has once achieved never decreases.

Examples2

Example 1
Input
```
3
30 60 90 150
BSG
```
Expected output
```
118
```
Example 2
Input
```
10
257 269 367 500
BSGGGGPPDD
```
Expected output
```
2499
```