* *deplasare la dreapta*: Presupunand ca puricele se afla pe pozitia $x$, atunci el se poate deplasa pe pozitia $x+1$, daca aceasta este libera, consumand o cantitate de energie $W$.
* *deplasare la stanga*: Presupunand ca puricele se afla pe pozitia $x$, atunci el se poate deplasa pe pozitia $x-1$, daca aceasta este libera, consumand o cantitate de energie $W$.
* *salt la dreapta*: Pentru a putea sari, puricele trebuie sa isi ia avant. Astfel, daca ultimele $K$ {$(K ≥ 1)$} miscari ale sale au fost toate deplasari la dreapta, atunci puricele poate sari intre $1$ si $K+1$ pozitii. Presupunand ca pozitia sa este $x$, dupa un salt la dreapta de $Q$ pozitii, puricele se va afla pe pozitia $x + Q$. Aceasta pozitie trebuie sa fie libera. Indiferent de numarul de pozitii peste care sare, puricele consuma o cantitate de energie $J$.

* *salt la stanga*: Daca ultimele $K$ {$(K ≥ 1)$} miscari ale puricelui au fost toate deplasari la stanga, atunci el poate sari intre $1$ si $K+1$ pozitii. Presupunand ca pozitia sa este $x$, dupa un salt la stanga de $Q$ pozitii, puricele se va afla pe poziÅ£ia $x - Q$. Aceasta pozitie trebuie sa fie libera. Indiferent de numarul de pozitii peste care sare, puricele consuma o cantitate de energie $J$.

* *salt la stanga*: Daca ultimele $K$ {$(K ≥ 1)$} miscari ale puricelui au fost toate deplasari la stanga, atunci el poate sari intre $1$ si $K+1$ pozitii. Presupunand ca pozitia sa este $x$, dupa un salt la stanga de $Q$ pozitii, puricele se va afla pe pozitia $x - Q$. Aceasta pozitie trebuie sa fie libera. Indiferent de numarul de pozitii peste care sare, puricele consuma o cantitate de energie $J$.

* *impingere la dreapta*: Presupunem ca puricele se afla pe pozitia $x$. Daca pozitia $x + 1$ contine un cub de zahar, atunci puricele poate impinge acest cub o pozitie la dreapta. In urma executarii acestei operatii, toate cuburile de pe pozitiile $x + 1, x + 2, ..., x + K - 1$, unde $x + K$ este prima pozitie libera din dreapta puricelui, se vor deplasa cu o pozitie la dreapta. Daca nu exista nici o pozitie libera la dreapta puricelui, atunci operatia nu este permisa. Pentru o impingere, puricele consuma o cantitate de energie $P$. In urma operatiei de impingere la dreapta, noua pozitie a puricelui va fi $x + 1$.
* *impingere la stanga*: Presupunem ca puricele se afla pe pozitia $x$. Daca pozitia $x - 1$ contine un cub de zahar, atunci puricele poate impinge acest cub o pozitie la stanga. In urma executarii acestei operatii, toate cuburile de pe pozitiile $x - 1, x - 2, ..., x - K + 1$, unde $x - K$ este prima pozitie libera din stanga puricelui, se vor deplasa o pozitie la stanga. Daca nu exista nici o pozitie libera la stanga puricelui, atunci operatia nu este permisa. Pentru o impingere, puricele consuma o cantitate de energie $P$. In urma operatiei de impingere la stanga, noua pozitie a puricelui va fi $x - 1$.

h2. Date de intrare

Pe prima linie a fisierului de intrare $purice.in$ se afla 4 numere intregi $N W J P$ (avand semnificatiile descrise mai sus). Pe cea de a doua linie a fisierului se afla o secventa de $N$ caractere din mulţimea ${0,1}$, ce descriu cele $N$ pozitii: $0$ inseamna ca pozitia respectiva este libera, iar $1$ ca este ocupata de un cub de zahar.

Pe prima linie a fisierului de intrare $purice.in$ se afla 4 numere intregi $N W J P$ (avand semnificatiile descrise mai sus). Pe cea de a doua linie a fisierului se afla o secventa de $N$ caractere din mult£imea ${0,1}$, ce descriu cele $N$ pozitii: $0$ inseamna ca pozitia respectiva este libera, iar $1$ ca este ocupata de un cub de zahar.

h2. Date de iesire

Pe prima linie a fisierului de iesire $purice.out$ veti afisa cantitatea minima de energie necesara puricelui pentru a ajunge pe poziţia $N$. Pe urmatoarele linii veti descrie miscarile efectuate de catre purice (cate o miscare pe linie). Miscarile vor fi codificate astfel:

Pe prima linie a fisierului de iesire $purice.out$ veti afisa cantitatea minima de energie necesara puricelui pentru a ajunge pe pozitia $N$. Pe urmatoarele linii veti descrie miscarile efectuate de catre purice (cate o miscare pe linie). Miscarile vor fi codificate astfel:

* $"WR"$ - pentru o deplasare la dreapta
* $"WL"$ - pentru o deplasare la stanga

* Initial, pozitiile $1$ si $N$ sunt libere.
* In cazul testelor folosite, va exista cel putin o succesiune valida de miscari ale puricelui care sa il aduca de pe pozitia $1$ pe pozitia $N$.
* La evaluare se vor folosi $20$ de teste. Punctajul pentru fiecare test se acorda in felul urmator:

** Daca succesiunea de miscari descrisa in fisierul de iesire nu este valida sau, in urma executarii ei, puri­cele nu ajunge pe pozitia $N$ sau cantitatea de energie consumata de purice in urma executarii tuturor miscarilor nu este egala cu numarul scris pe prima linie a fisierului de iesire, veti primi $0$ puncte

** Daca succesiunea de miscari descrisa in fisierul de iesire nu este valida sau, in urma executarii ei, puri­cele nu ajunge pe pozitia $N$ sau cantitatea de energie consumata de purice in urma executarii tuturor miscarilor nu este egala cu numarul scris pe prima linie a fisierului de iesire, veti primi $0$ puncte

** Altfel, sa presupunem ca $M$ este cantitatea minima de energie consumata de purice pentru a ajunge in pozitia finala si $A$ este cantitatea de energie determinata de programul dumneavoastra
*** Daca $A = M$, veti primi $5$ puncte
*** Daca $M < A ≤ 1.15*M$, veti primi $4$ puncte