pipe

Gigel trebuie să proiecteze instalaţia de apă din propria curte. Curtea are dimensiuni infinite şi nu este împrejmuită. El cunoaşte coordonatele punctului în care se află sursa de apă şi coordonatele punctului unde va instala un robinet. Conducta trebuie proiectată astfel încât cele două puncte să fie unite. Pentru aceasta dispune de $n$ ţevi sub forma unor segmente ale căror lungimi se cunosc, dar care nu pot fi tăiate. Două ţevi se vor conecta astfel încât unghiul dintre ele să fie de $90 \degree$, $180 \degree$, $270 \degree$ sau $360 \degree$, adică orice cuplare pe orizontală sau verticală (sus, jos, stânga, dreapta). Unele ţevi sunt roşii iar altele sunt vopsite în albastru. Cele roşii se pot conecta doar pe verticală iar cele albastre doar pe orizontală. Pot exista ţevi de aceeaşi culoare şi lungimi egale, dar fiecare ţeavă se va folosi în instalaţie o singură dată.

Cerinţă

Scrieţi un program care să determine lungimea minimă de ţeavă necesară pentru a uni cele două puncte.

Date de intrare

Fişierul pipe.in are următorul format:

• pe prima linie numărul $n$;
• pe următoarea linie coordonatele carteziene ale sursei de apă $x_i$, $y_i$, numere naturale separate printr-un spaţiu;
• pe următoarea linie coordonatele carteziene ale punctului unde va fi plasat robinetul $x_f$, $y_f$, numere naturale separate printr-un spaţiu;
• pe următoarele $n$ linii descrierea fiecărei ţevi realizată astfel: caracterul A pentru culoarea albastru sau R pentru culoarea roşu, urmat de spaţiu şi apoi de un număr natural reprezentând lungimea ţevii.

Date de ieșire

Fişierul pipe.out va conţine pe prima linie un număr reprezentând lungimea minimă determinată sau cuvântul imposibil dacă nu se poate realiza conectarea cu ţevile disponibile.

Restricții și precizări

• $1 \leq n \leq 100$
• $1 \leq$ lungimea fiecărei ţevi $\leq 290$
• $0 \leq x_i, y_i, x_f, y_f \leq 32 \ 000$

Exemplu

pipe.in

8
2 3
6 8
A 9
R 3
R 13
R 8
A 2
R 4
A 15
R 12

pipe.out

37

Explicație