Codah ClubTrain. Submit. Improve.
Sign in
English
#000399

Autoput1

Imagine one simple road in a coordinate system. Road is going from left to right, following the configuration of the land and within one square it can:
a) stay on the same height
b) go down or up by one square
Car is driving on the road from left to right. The time needed to travel through a single square is either A seconds for the case a), or B seconds for the case b).However, we can build a tunnel under some mountain or a viaduct above some valley. These objects have to be horizontal, and the time needed for a car to travel through a single square on a tunnel or viaduct is [] seconds.Write a program that will, for a given configuration of land, calculate the minimal time for a car to travel the whole road with optimal construction of tunnels and viaducts. Total number of objects built must not be greater than the given number K.


Image: autoput

Figure above corresponds to the third example. Original road is denoted by the thin line, and the optimal path is denoted by the thick line. Because the number of objects is restricted to 2, we could not build a tunnel under the first mountain.


InputFirst line of input contains three integers A, B and C, 1 ≤ A,B,C ≤ 100.Second line of input contains two integers N and K, 1 ≤ N ≤ 100,000, 1 ≤ K ≤ 300.Third line of input contains a sequence of N characters that describes the configuration of the land, from left to right. Each character in the sequence is one of the following:
'D' in next square land is going DOWN
'R' in next square land is staying on the SAME HEIGHT
'G' in next square land is going UP

OutputFirst and only line of output should contain the minimal time from the problem statement.


Input
[c]3 2 1
9 1
GGDGGDDRR
Output
16

Input
3 5 4
10 10
RGDRDRRRRG
Output
36

Input
10 20 15
16 2
RGRDGGDDRRDDRDGG
Output
235

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.