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ă (≥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ța

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 ≤ N ≤ 5000
• -109 ≤ abscisele punctelor ≤ 109
• 0 ≤ ordonatele punctelor ≤ 109
• 0 ≤ costurile segmentelor ≤ 109
• 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

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("laser.in");
ofstream fout ("laser.out");

typedef long long ll;
const int Nmax = 5005;
const ll inf = 1e18;

int x, y, i, j, n, cost;
ll dp[Nmax], ans;

struct point
{
    int x, y;
} A, B;

bool cmp(point A, point B) /// sortare antitrigonometrica
{
    if(!A.y && !B.y) return A.x < B.x;
    if(!A.y) return A.x < 0;
    if(!B.y) return B.x > 0;
    return (ll) A.x * B.y < (ll) A.y * B.x;
}

bool cmp2(point A, point B)
{
    if(!A.y && !B.y) return (ll) A.x * B.x > 0;
    if(!A.y) return A.x < 0;
    if(!B.y) return B.x > 0;
    return (ll) A.x * B.y <= (ll) A.y * B.x;
}

struct segment
{
    point start, finish; int w;
} a[Nmax];

int main()
{
    fin >> n;
    for(i=1; i<=n; ++i)
    {
        fin >> A.x >> A.y >> B.x >> B.y >> cost;
        if(cmp(B, A)) swap(A, B);
        a[i] = {A, B, cost};
    }

    for(i=1; i<=n; ++i)
        for(j=i+1; j<=n; ++j)
            if(cmp(a[j].start, a[i].start)) swap(a[i], a[j]);

    for(i=1; i<=n; ++i)
        if(a[i].start.x < 0 && a[i].start.y == 0) dp[i] = a[i].w; /// plec din cadranul 2, de pe axa Ox
            else
            {
                dp[i] = inf;
                for(j=1; j<i; ++j)
                    if(cmp2(a[i].start, a[j].finish))
                        dp[i] = min(dp[i], dp[j] + a[i].w);
            }

    ans = inf;
    for(i=1; i<=n; ++i)
        if(a[i].finish.x >  0 && a[i].finish.y == 0) ans = min(ans, dp[i]); /// termin in cadranul 1, pe axa Ox
    fout << (ans < inf ? ans : -1) << '\n';

    return 0;
}