Simulare ONI 2018 | laser

Considerăm $N$ segmente în plan identificate prin coordonatele extremităților lor. Toate segmentele sunt închise, adică fiecare conține și cele două puncte considerate extremitățile sale. Presupunem că în punctul $O(0,0)$ care este originea sistemul de axe ortogonale $XOY$, se află un laser care poate transmite câte un fascicul de lumină în orice punct cu ordonata pozitivă $(\geq 0)$. Fasciculul poate fi reprezentat în plan, ca o semidreaptă cu extremitatea în originea axelor. Totuși, dacă fasciculul de lumină întâlnește un segment, acesta îl obturează, adică îl împiedică să treacă mai departe de acesta. Considerăm că fiecare segment are asociat un număr care reprezintă un cost pentru desenarea lui în plan.

Cerință

Determinaţi costul total minim al segmentelor care pot fi alese pentru a obtura orice fascicul de lumină care ar pleca din origine către un punct cu ordonata pozitivă.

Date de intrare

Fișierul de intrare laser.in conține pe prima linie numărul natural $N$ de segmente. Pe următoarele $N$ linii se află câte cinci numere întregi $x1, y1, x2, y2$ cost, separate prin câte un spațiu. Primele patru numere reprezintă coordonatele extremităților fiecărui segment, pentru fiecare dintre ele în ordine abscisa și ordonata, iar ultimul număr de pe linie reprezintă costul segmentului.

Date de ieșire

Fișierul de ieșire laser.out va conține un număr reprezentând costul minim determinat sau $-1$ dacă nu există soluție.

Restricții și precizări

• $1 \leq N \leq 5 \ 000$
• $-10^9 \leq$ abscisele punctelor $\leq 10^9$
• $0 \leq$ ordonatele punctelor $\leq 10^9$
• $0 \leq$ costurile segmentelor $\leq 10^9$
• Se garantează că punctul $O(0,0)$ nu se află pe niciunul din cele $N$ segmente
• La evaluare se vor folosi fișiere de intrare în valoare de $30$ de puncte care au pentru toate segmentele costul egal cu $1$

Exemplul 1

laser.in

4
2 3 5 0 2
2 3 -4 4 1
-2 4 -5 0 1
6 0 -14 1 8

laser.out

4

Explicație

S-au ales segmentele de cost total minim $[(-5, 0), (-2,4)], [(-4, 4), (2,3)]$ și $[(2, 3), (5,0)]$. Segmentele $[(-5, 0), (-2,4)]$ și $[(-14, 1), (6,0)]$ obturează orice fascicul dar are cost total mai mare

Exemplul 2

laser.in

4
-1 3 1 3 1
-2 0 -1 1 1
2 0 1 1 1
1 1 -1 1 1

laser.out

3

Explicație

S-au ales segmentele: $[(-2, 0), (-1,1)], [(-1, 1), (1,1)], [(1, 1), (2,0)]$.

Exemplul 3

laser.in

3
-1 3 1 3 1
-2 0 -1 1 4
2 0 1 1 5

laser.out

-1

Explicație

Nu există segmente care să respecte cerințele.