„MARVEL AT HIS MIGHT!”

Cerința

Zoli și D’Umbră s-au pierdut din nou prin labirintul cu n x n camere dispuse pe n linii și n coloane. De această dată, amândoi se află în camera (1, 1). A mai trecut de ultima dată și cateva lucruri s-au schimbat. Ei îl au acum la dispoziție pe Memobot, un roboțel controlat prin telecomandă care poate primi secvențe de comenzi. Când roboțelul primeste o secvență de comenzi, acesta va respecta fiecare comandă din secvență, apoi va aștepta o nouă comandă.

Din păcate pentru ei, Dr. Boom s-a plictisit să trimită Boom Bots (niște roboței care explodează singuri) să-i enerveze pe eroii din Azeroth. Așadar, acesta îi poziționează în câteva camere din labirint și care vor exploda când se vor afla în cameră cu înca cineva.

Acum Zoli și D’Umbră vor trebui să îl trimită pe Memobot pentru a curăța drumul până la ieșirea aflată în camera (n, n). Ajutați-i să iasă din labirint pe drumul cel mai scurt parcurs de Memobot! (Drumul cel mai scurt este, bineînțeles, cel ce conține un număr minim de secvențe de comenzi)

Date de intrare

Fișierul de intrare labirint2.in conține pe prima linie numerele n (dimensiunea labirintului), b (numărul de Boom Bots pe care Dr. Boom îi poziționează în labirint), s (numărul de secvențe de comenzi) și k (numărul de comenzi din fiecare secvență).

Pe următoarele b linii se află câte o pereche de numere naturale x și y reprezentând faptul că Dr. Boom a trimis un Boom Bot în camera aflată la coordonatele (x, y).

Pe următoarele s linii se află cate k litere din mulțimea {'U', 'D', 'L', 'R'} care reprezintă direcția spre care se va deplasa Memobot în secvență. (U – Sus, D – Jos, L – Stânga, R – Dreapta).

Date de ieșire

Fișierul de ieșire labirint2.out va conține pe prima linie numărul S, reprezentând numărul minim de secvențe de comenzi pe care Memobot trebuie să le primească.

Restricții și precizări

• 1 ≤ n ≤ 400
• 1 ≤ b ≤ n * n
• 1 ≤ k, s ≤ 10
• Ordinea comenzilor din fiecare secvență nu poate fi schimbată!
• Memobot poate trece de două ori prin aceeași cameră.
• Pentru 30% din teste, k = 1, s = 4 și secvențele sunt diferite între ele. (Memobot va putea merge pe direcțiile simple: Dreapta, Stânga, Sus și Jos)
• Dacă Memobot primește o secvență de comenzi care îl conduc spre o cameră inexistentă (pe linia/coloana 0 sau n + 1), atunci Memobot nu va executa secvența.
• Dacă cel puțin 2 Boom Bots se află într-o cameră, aceștia vor exploda înainte ca Memobot să pornească.
• Dacă nu există nici un drum prin care Memobot să ajungă în camera (n, n), atunci se va afișa mesajul ”Imposibil!”
• Personajul este D’Umbră și nu Dumbră, și Dr. Boom este sigur de acest lucru.

Exemplu:

labirint2.in

4 3 4 2
3 2
3 3
4 1
D R
D L
U R
D D

labirint2.out

4

Explicație

Comenzile sunt, în această ordine: (D, R), (U, R), (D, R), (D, D)