Editing 4141 - Autostrada 1 (section)

== Cerința ==
Gimi tocmai a câștigat o licitație pentru asfaltarea unei noi autostrăzi. Firma lui este responsabilă de prelucrarea zonelor dintr-o suprafață bidimensională de dimensiuni N × N. Știm că dacă un drum va trece prin a i-a linie, respectiv a j-a coloană, atunci acea zonă de la poziția (i, j) va trebui asfaltată. Liniile și coloanele suprafeței bidimensionale sunt numerotate de la 1 la N. Din nefericire pentru el, a aflat abia după semnarea contractului că proiectul nu este așa de simplu precum a crezut. Drumul va fi determinat de traseul
urmat de o dronă. Mai mult, Gimi nici nu știe acest traseu, dar a primit de la proiectantul autostrăzii poziția inițială a dronei (ls, cs), reprezentând linia și coloana zonei în care se află inițial drona, și o listă de K instrucțiuni pe care acesta le-a aplicat dronei.
Fiecare instrucțiune este o pereche de tipul (dir, p), cu semnificația că drona s-a deplasat pe direcția dir cu p unități, unde dir poate avea următoarele valori:

0 – direcția Nord
1 – direcția Est
2 – direcția Sud
3 – direcția Vest
Spre exemplu, dacă drona se află în poziția (1, 3) și a primit instrucțiunea (2, 3), atunci drona se va deplasa spre sud (direcția 2) cu 3 unități și va parcurge zonele (2, 3), (3, 3) și (4, 3) unde se va opri. Toate aceste zone vor trebui asfaltate de firma lui Gimi.

Costul de asfaltare al unei zone prin care trece un drum simplu este Cz. Din fericire pentru Gimi, o zonă parcursă de mai multe ori de dronă trebuie asfaltată o singură dată. Însă, el a observat că pot apărea niște cazuri particulare:

Dacă într-o zonă se produce o intersecție de tip ⊤, înseamnă că este nevoie de benzi de accelerare/decelerare în intersecție. Atunci costul de asfaltare al zonei devine Ct.
Dacă într-o zonă se produce o intersecție de tip +, înseamnă că este nevoie de construirea unui pod, caz în care costul de asfaltare al zonei devine Cp.
Având aceste informații, Gimi vrea să verifice dacă traseul dronei este valid, adică drona nu va părăsi niciodată suprafața de care este responsabilă firma lui Gimi. În cazul în care traseul este invalid Gimi vrea să știe a câta instrucțiune dintre cele K a determinat mutarea dronei în afara suprafeței. Dacă traseul este valid, el vrea să determine costul total de asfaltare al autostrăzii.