== include(page="template/taskheader" task_id="stalpi") ==

Poveste si cerinta...

O anumita strada din Orasul Efemer poate fi privita ca axa $Ox$ a numerelor naturale. De-a lungul acestei strazi se afla $N$ stalpi de iluminare publica. Al $i$-lea stalp se afla la coordonata $X{~i~}$ si pentru o suma de $C{~i~}$ lei se poate amplasa un bec in interiorul stalpului, care va lumina $S{~i~}$ metri in stanga stalpului si $D{~i~}$ metri in dreapta stalpului. Primarul orasului vrea ca toti stalpii sa fie vizibili. Un stalp este vizibil daca in interiorul lui este amplasat un bec sau daca se afla in raza de iluminare a altui stalp in care s-a amplasat un bec. Ajutati primarul afland costul minim necesar pentru ca toti stalpii din Orasul Efemer sa fie vizibili.

h2. Date de intrare

Fisierul de intrare $stalpi.in$ ...

Fisierul de intrare $stalpi.in$ contine pe prima linie numarul $N$ avand semnificatia din enunt. Pe urmatoarele $N$ linii urmeaza cate un cvadruplu $x c s d$ cu semnificatia ca stalpul $i$ se afla la coordonata $x$, costul pentru a amplasa un bec in interiorul lui este $c$ si daca se realizeaza acest lucru va lumina $s$ metri in stanga si $d$ metri in dreapta.

h2. Date de iesire

In fisierul de iesire $stalpi.out$ ...

Pe prima linie a fisierului de iesire $stalpi.out$ se afla un numar natural $MIN$ reprezentand costul minim necesar pentru ca toti stalpii din oras sa fie vizibili.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ X{~i~}, S{~i~}, D{~i~} ≤ 10^9^$
* $1 ≤ C{~i~} ≤ 100 000$
* Daca se amplaseaza un bec in stalpul $i$ el va lumina orice stalp $j$ cu proprietatea $X{~i~}-S{~i~}≤X{~j~}≤X{~i~}+D{~i~}$
* Toate numerele din fisierul de intrare sunt naturale
* Datorita infrastructurii ciudate a stalpilor un bec poate fi amplasat in interiorul acestora

h2. Exemplu
table(example). |_. stalpi.in |_. stalpi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
  3 1 3 5
  1 10 10 9
  7 2 5 3
  10 18 4 4
| 3

|
h3. Explicatie

...

Se va amplasa un bec in interiorul stalpilor $1$ si $3$. Stalpul $2$ va fi luminat de stalpul $1$ iar stalpul $4$ va fi luminat de stalpul $3$.

== include(page="template/taskfooter" task_id="stalpi") ==