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

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. El s-a decis sa aleaga o multime de stalpi si sa instaleze cate un bec in fiecare dintre acestia. Problema este ca va trebui sa plateasca pentru fiecare stalp costul necesar amplasarii unui bec in stalpul respectiv si vrea ca suma acestor costuri sa fie minima. Ajutati primarul afland costul minim necesar pentru ca toti stalpii din Orasul Efemer sa fie vizibili.

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. El s-a decis sa aleaga o multime de stalpi si sa instaleze cate un bec in fiecare dintre acestia. Problema este ca va trebui sa plateasca pentru fiecare stalp ales costul necesar amplasarii unui bec in stalpul respectiv si vrea ca suma acestor costuri sa fie minima. Ajutati primarul afland costul minim necesar pentru ca toti stalpii din Orasul Efemer sa fie vizibili.

h2. Date de intrare