MVP Diamond (Normal)

Interview

Time limit1sMemory limit512 MB

Summary

Given the monthly MVP tiers over N months and the tier thresholds, find the maximum total spending that produces exactly those tiers.

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

Problem

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

Sangmin enjoys spending money in the game MapleLeaf Story. MapleLeaf Story has 'MVP tiers' that give benefits based on how much money you spend.

There are five MVP tiers, Bronze(B), Silver(S), Gold(G), Platinum(P), Diamond(D), and a tier is determined by the amount spent in the current month and the previous month, that is, over the most recent 2 months including the current month.

MapleLeaf Story has a 'maximum spending limit' to prevent excessive spending, so you can spend at most the Diamond tier threshold in one month, and spending is possible only in units of ten thousand won.

An MVP tier is computed and assigned when the month ends. For example, suppose the tier thresholds are as in the table below and Sangmin, who started the game in January, spent 300,000 won in January, 200,000 won in February, and 500,000 won in March. Then January (300,000) and February (300,000+200,000=500,000) are assigned Silver, and March (200,000+500,000=700,000) is assigned Gold.

MVP tier (notation)	Tier threshold	Spending 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 a lot of cash over N months since starting the game. He kept this fact strictly secret from his girlfriend. His girlfriend hated that he spent money on the game. Then one day a problem arose. The MVP tier record for N months leaked to Sangmin's girlfriend!

Sangmin's girlfriend asked you to trace back how much he spent.

Sangmin's girlfriend: Tell me the maximum amount Sangmin could have spent on the game.

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

Input

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

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

The third line gives the MVP tiers from the first month to the N-th month of play, using the tier notations. The case where the given MVP tiers cannot be achieved is not given.

Output

Print the maximum total spending, in units of ten thousand won, that achieves the given MVP tiers.

Constraints

1 ≤ N ≤ 36

0 < s < g < p < d ≤ 500

Examples2

Example 1
Input
```
8
30 60 90 150
BSDDPGSG
```
Expected output
```
506
```
Example 2
Input
```
10
257 269 367 500
BSGGGGPPDD
```
Expected output
```
2499
```