Duž jednog puta koji je prav nalazi se Tomina kuća. Duž tog puta nalazi se i n svetiljki, svaka sa

• određenom koordinatom,
• dometom osvetljavanja
• potrošnjom u jedninici vremena.

Tomina kuća ima koordinatu 0. Koordinata svetiljke označava poziciju svetiljke u odnosu na Tominu kuću. Ukoliko je koordinata svetiljke neki broj x tada se

• ukoliko je x broj veći ili jednak 0 svetiljka nalazi x metara desno od Tomine kuće
• ukoliko je x manje od 0 svetiljka nalazi x metara levo od Tomine kuće

Domet osvetljavanja neke svetiljka je broj koji označava koliko metara levo i desno od te svetiljke je put osvetljen pomoću nje. Ukoliko je domet neke svetiljke neko x a njena koordinata neko y put je od kordinate y-x do y+x osvetljen pomoću te svetiljke.

Potrošnja u jedinici vremena neke svetiljke je broj koji označava koliko džula energije u jedinici vremena troši ta svetiljka kada je upaljena.

Na početku su sve svetiljke ugašene. Toma želi, tako što će upaliti neke svetiljke, da osvetli put u kontinuitetu od koordinate A do koordinate B (A<B) tako da potrošnja energije u jedinici vremena bude minimalna.

(Toma želi samo da sve tačke puta počev od tačke sa koordinatom A do tačke sa koordinatom B budu osvetljene, ne zanima ga da li će još neki delovi puta koji su izvan ovog intervala biti osvetljeni)

Ulaz:

(Ulazni podaci se nalaze u datoteci svetiljke.in) U prvom redu tekstualne datoteke nalaze se redom brojevi n, A i B ( n je prirodan broj manji ili jednak 10⁵ dok su A i B celi brojevi koji su veći ili jednaki -2x10⁹ i manji ili jednaki 2x10⁹ i A<B) U svakom od sledećih n redova nalaze se po tri cela broja koji opisuju jednu svetiljku. Ti brojevi su redom koordinata svetiljke (ceo broj veći ili jednak -10⁹ i manji ili jednak 10⁹), domet osvetljavanja (prirodan broj manji ili jednak 10⁹) i potrošnja u jedinici vremena (prirodan broj manji ili jednak 20000). (U redu čiji je redni broj i+1 nalazi se opis i-te svetiljke)

Izlaz:

(Izlazne podatke upisati u datoteku svetiljke.out) U izlaznoj datoteci treba upisati broj koji označava minimalnu potrošnju energije u jedinici vremena koja se mora potrošiti da bi se osvetlio deo puta koji Toma želi ukoliko je to moguće. Ukoliko to nije moguće upisati -1.

U 50% test primera n je manje ili jednako 5000.

Primer 1:

6 -10 20
-8 4 2
25 4 7
3 10 1
0 15 4
17 3 5
16 4 2

5

Objašnjenje.

Moguće je osvetliti deo puta od koordinate -10 do koordinate 20. Minimalna potrošnja energije u jedinici vremena koja se mora imati da bi se do izvelo je 5 i ona se dobija paljenjem 1. , 3. i 6. svetiljke. (1. svetiljka osvetljava interval od -12 do -4 , 3. svetiljka osvetljava interval od -7 do 13 a 6. svetiljka osvetljava interval od 12 od 20)

Primer 2:

3 4 20
8 5 10
8 4 7
19 4 10

-1

#include <stdio.h>
#include <stdlib.h>

struct el
{
  int levo,desno,potrosnja;
};

el *A;
int n;
int *P,*Min;
int *V;
int levo,desno;
int m;
int br;
el *AA;
int nn;

void unos()
{
  FILE *f;
  f=fopen("svetiljke.in","r");
  fscanf(f,"%d%d%d",&n,&levo,&desno);
  A=(el *)malloc(n*sizeof(el));
  int i,br1,br2;
  for (i=0;i<n;i++)
  {
    fscanf(f,"%d%d%d",&br1,&br2,&A[i].potrosnja);
    A[i].levo=br1-br2;
    A[i].desno=br1+br2;
  }
  fclose(f);
}

void f1()
{
  int tren=0;
  while (tren<n)
  {
    if (A[tren].desno<=levo || A[tren].levo>=desno)
    {
      A[tren]=A[n-1];
      n--;
    }
    else
    {
      if (A[tren].levo<levo)
        A[tren].levo=levo;
      if (A[tren].desno>desno)
        A[tren].desno=desno;
      tren++;
    }
  }
}

void sort(el *A,int n)
{
  int pom=A[n/2].desno,levo=0,desno=n-1;
  while (levo<=desno)
  {
    while (A[levo].desno<pom)
      levo++;
    while (A[desno].desno>pom)
      desno--;
    if (levo<=desno)
    {
      el pom;
      pom=A[levo];
      A[levo]=A[desno];
      A[desno]=pom;
      levo++;
      desno--;
    }
  }
  if (desno>0)
    sort(A,desno+1);
  if (levo<n-1)
    sort(A+levo,n-levo);
}

void ispis(int broj)
{
  FILE *f=fopen("svetiljke.out","w");
  fprintf(f,"%d",broj);
  fclose(f);
}

int bp(int broj)
{
  int tren,levo=0,desno=m-1;
  
  while (true)
  {
    tren=(levo+desno)/2;
    if (P[tren]<broj)
      levo=tren+1;
    if (P[tren]>broj)
      desno=tren-1;
    if (P[tren]==broj)
      return tren;
    if (desno<levo)
      if (P[desno]<broj)
        return desno+1;
      else
        return desno;
  }
}

int mmin(int br1,int br2)
{
  if (br1<br2)
    return br1;
  else
    return br2;
}

void stablo(int m)
{
  br=1;
  while (br<m)
    br*=2;
  V=(int *)malloc((br*2-1)*sizeof(int));
  V[br-1]=0;
  int i;
  for (i=br;i<2*br-1;i++)
    V[i]=2000000000;

  for (i=br-2;i>=0;i--)
    V[i]=mmin(V[i*2+1],V[i*2+2]);
}

int najmanji(int levo,int desno)
{
  levo=br-1+levo;
  desno=br-1+desno;
  int broj=mmin(V[levo],V[desno]);
  int da_levo,da_desno;
  da_levo=levo%2;
  levo=(levo-1)/2;
  da_desno=(desno+1)%2;
  desno=(desno-1)/2;
  while (levo<desno)
  {
    if (da_levo)
      if (V[levo*2+2]<broj)
        broj=V[levo*2+2];
    if (da_desno)
      if (V[desno*2+1]<broj)
        broj=V[desno*2+1];
    da_levo=levo%2;
    levo=(levo-1)/2;
    da_desno=(desno+1)%2;
    desno=(desno-1)/2;
  }
  return broj;
}

void ubaci(int poz,int vred)
{
  V[br-1+poz]=vred;
  int tren=(br-1+poz-1)/2;
  while (tren>0)
  {
    V[tren]=mmin(V[tren*2+1],V[tren*2+2]);
    tren=(tren-1)/2;
  }
  V[0]=mmin(V[1],V[2]);
}

int main()
{
  unos();
  f1();  
  if (n==0)
  {
    ispis(-1);
    return 0;
  }
  if (n>1)
    sort(A,n);
  if (desno>A[n-1].desno)
  {
    ispis(-1);
    return 0;
  }
  
  int i;
  P=(int *)malloc((n+1)*sizeof(int));
  P[0]=levo;
  P[1]=A[0].desno;
  m=1;
  for (i=1;i<n;i++)
    if (A[i].desno>P[m])
    {
      m++;
      P[m]=A[i].desno;
    }
  m++;
  Min=(int *)malloc(m*sizeof(int));
  Min[0]=0;
  for (i=1;i<m;i++)
    Min[i]=2000000000;
  stablo(m);
  
  int tren=0;
  for (i=1;i<m;i++)
  {
    bool da=true;
    int broj=0;
    while (da)
    {
      broj++;
      if (tren==n)
        da=false;
      else
        if (A[tren].desno==P[i])
        {
          int br1,br2;
          br1=bp(A[tren].levo);
          br2=bp(A[tren].desno)-1;
          if (br1<=br2)
          {
            int br=najmanji(br1,br2);
            if (br+A[tren].potrosnja<Min[i])
              Min[i]=br+A[tren].potrosnja;
          }
          tren++;
        }
        else
        {
          ubaci(i,Min[i]);
          da=false;
        }
    }
  }
  if (Min[m-1]<2000000000)
    ispis(Min[m-1]);
  else
    ispis(-1);
  return 0;
}