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.

Cerința

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.

Date de intrare

Prima linie din fișierul de intrare autostrada.in va conține patru numere naturale N, K, ls și cs, unde N este dimensiunea suprafeței, K este numărul de instrucțiuni aplicate dronei, iar (ls, cs) reprezintă linia și coloana zonei în care se află inițial drona. A doua linie va conține trei numere naturale Cz, Ct și Cp, reprezentând costurile de asfaltare ale unei zone simple, unei intersecții de tip ⊤, respectiv unei intersecții de tip +. Următoarele K linii vor conține câte două numere naturale diri și pi, reprezentând valorile specifice celei de-a i-a instrucțiuni primite de dronă. Numerele scrise pe aceeași linie sunt separate printr-un singur spațiu.

Date de ieșire

Dacă traseul dronei este invalid, pe prima linie din fișierul de ieșire autostrada.out se va afișa textul
TRASEU INVALID, iar apoi, pe a doua linie, un singur număr natural, reprezentând a câta instrucțiune dintre cele K a determinat mutarea dronei în afara suprafeței. Altfel, pe prima linie din fișierul de ieșire se va afișa textul TRASEU VALID, iar apoi, pe a doua linie, un singur număr natural reprezentând costul total necesar pentru asfaltarea autostrăzii.

Restricții și precizări

• 2 ≤ N ≤ 2000
• 1 ≤ K ≤ 1.000.000
• 1 ≤ ls, cs ≤ N
• 1 ≤ Cz, Ct, Cp ≤ 100
• diri ∈ {0, 1, 2, 3} pentru orice 1 ≤ i ≤ K
• 1 ≤ pi ≤ N pentru orice 1 ≤ i ≤ K
• Poziția inițială și poziția finală a dronei trebuie asfaltate.
• Datorită testelor mari, doar unele au fost adăugate

Exemplul 1:

autostrada.in

3 3 1 1
1 2 3
1 2
2 3
3 1

autostrada.out

TRASEU INVALID
2

Explicație

Cu verde s-au marcat zonele ce trebuiesc asfaltate, iar cu linii albe s-a indicat traseul dronei. Zonele gri sunt zone nevizitate de traseul dronei. A doua instrucțiune este invalidă, drona ieșind din suprafață întrucât ar ajunge in coordonatele (4, 3).

Exemplul 2:

autostrada.in

5 7 2 1
1 2 3
1 4
2 2
3 3
0 3
1 2
2 1
3 3

autostrada.out

TRASEU VALID
17

Explicație

Traseul determinat de dronă este:

Se observă că toate zonele, mai puțin (2, 2) și (2, 4) sunt simple, adică nu sunt intersecții, și fiecare au
costul de asfaltare Cz = 1. În (2, 2) avem o intersecție de tip +, deci costul de asfaltare va fi Cp = 3.
În (2, 4) avem o intersecție de tip ⊤, deci costul de asfaltare va fi Ct = 2. În total, costul este 12 × 1 + 1 × 2 + 1 × 3 = 17.