h2. Date de intrare

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.

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$ (pe linia $i+1$ exista informatii despre 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

* $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~}$

* Nu exista doi stalpi diferiti care sa aibe aceiasi coordonata $X$

* Toate numerele din fisierul de intrare sunt naturale
* In cel putin $40%$ din teste $1 ≤ N ≤ 1000$
* Datorita infrastructurii ciudate a stalpilor un bec poate fi amplasat in interiorul acestora

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

2721