Blue and Green is a fictitious sandbox game where you have a line of blue and green marbles. There exists a currency in this game, which you can use to change the assortment of marbles. Each move has its own cost. The following moves are:
- set the colour of a single marble at a cost of ~S~
- rotate all the marbles to the left by 1 (the left-most marble moves to the right end, and everything else moves one place to the left) at a cost of ~L~
- rotate all the marbles to the right by 1 (the right-most marble moves to the left end, and everything else moves one place to the right) at a cost of ~R~
- invert the colour of all the marbles at a cost of ~I~
Find the number of different arrangements of blue and green marbles that can be achieved by using ~M~ or less currency units. All blue marbles are not distinguishable from each other and the same goes for green marbles. This means that if you have the arrangement
GBGBGB and you rotate it twice to get
GBGBGB, the original and final arrangements are indistinguishable (equivalent).
Hint: try the steps in the listed order for efficiency.
The first line contains two space separated integers ~N~ ~(1 \le N \le 20)~, the number of marbles and ~M~, the amount of currency.
The second line contains four space separated integers ~S~, ~L~, ~R~ and ~I~.
The third line contains a string with ~N~ characters,
B for a blue marble or
G for a green marble.
~(1 \le S, L, R, I, M \le 100)~ Note: Test cases are reasonable.
Subtask 1 [5%]
~N \le 5~
Subtask 2 [5%]
~N \le 10~
Subtask 3 [90%]
~N \le 20~
A single integer - the number unique marble arrangements achievable with the amount of currency.
Sample Input 1
2 1 1 2 2 2 BB
Sample Output 1
Explanation for Sample Output 1
You can only afford to set the colour of one marble. Thus, you can change the colour of the first or second marble to get the possible arrangements:
Sample Input 2
4 1 1 1 1 1 BGGG
Sample Output 2
Explanation for Sample Output 2
You can afford one of the moves. Thus, we get the following unique arrangements:
GGGGsetting the first marble to green
BBGGsetting the second marble to blue
BGBGsetting the third marble to blue
BGGBsetting the fourth marble to blue
GBGGrotating the marbles right once
GGGBrotating the marbles left once
GBBBinverting all the colours
Sample Input 3
5 5 3 4 4 2 BGGBB
Sample Output 3