Highway

A road consists of N unit sections from left to right. On each section the road either stays at the same height, rises by 1, or descends by 1.

The time needed for a car to travel one unit section of the original road is as follows.

• A seconds if the height stays the same
• B seconds if the height changes by 1

You may build tunnels under mountains and viaducts over valleys. Each structure must be horizontal, starting at some position and ending at the first later position with the same height. Traveling one unit length through a tunnel or over a viaduct takes C seconds.

You may build at most K structures in total. Given the terrain, compute the minimum time needed for the car to travel across the whole road.

The figure shows the third public test. The thin line is the original road, and the thick line is an optimal route. Since at most 2 structures may be built there, no tunnel is built under the first mountain.

The first line contains three integers A, B, and C. Each value is between 1 and 100, inclusive.

The second line contains two integers N and K, where 1 ≤ N ≤ 30,000 and 1 ≤ K ≤ 1,000.

The third line contains a string of length N describing the terrain from left to right. Each character has one of the following meanings.

• D: the terrain goes down by 1 on the next unit section.
• R: the terrain stays at the same height on the next unit section.
• G: the terrain goes up by 1 on the next unit section.

Print the minimum time needed for the car to travel across the whole road.