Autoput1

Zamislimo pojednostavljeni autoput u koordinatnom sustavu. Cesta ide slijeva na desno, prati konfiguraciju terena i prilikom prelaska svakog jediničnog kvadratića može:
a) ostati na istoj visini
b) spustiti se ili popeti se za jedan kvadratić
Automobil vozi po cesti slijeva na desno, a vrijeme potrebno da prijeđe jedan kvadratić iznosi A sekundi za slučaj a), a B sekundi za slučaj b).Međutim, mi ispod nekih planina ili iznad nekih ponora možemo prokopati tunel odnosno izgraditi vijadukt. Oni moraju biti vodoravni, a vrijeme potrebno da automobil prijeđe jedan kvadratić kroz tunel odnosno preko vijadukta iznosi [] sekundi.Napišite program koji će za zadanu konfiguraciju terena izračunati minimalno vrijeme potrebno da automobil prijeđe cijeli autoput uz optimalnu izgradnju tunela i vijadukata. Pri tome ukupan broj izgrađenih tunela i vijadukata ne smije biti veći od K.

Na gornjoj slici se nalazi treći test primjer. Tankom crtom označen je prvobitni autoput, dok je debelom crtom označen optimalni put na kojem je izgrađen jedan tunel i jedan vijadukt. Kako je broj tunela i vijadukata ograničen na maksimalno dva, nismo mogli izgraditi i tunel ispod prve planine, iako bi nam se to isplatilo.

InputU prvom retku se nalaze tri prirodna broja A,B i C, 1 ≤ A,B,C ≤ 100.U drugom retku se nalaze dva prirodna broja N i K, 1 ≤ N ≤ 100000 (sto tisuća), 1 ≤ K ≤ 300.U trećem retku se nalazi niz od N znakova koji opisuju izgled autoceste, slijeva na desno. Znakovi koji se mogu pojaviti su:
'D' teren se u sljedećem kvadratiću spušta prema DOLJE
'R' teren je u sljedećem kvadratiću RAVAN
'G' teren se u sljedećem kvadratiću penje prema GORE

OutputU prvi i jedini redak treba ispisati traženo minimalno vrijeme iz teksta zadatka.