carnati

Carnati

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

Gigel vrea sa deschida un magazin de carnati. Pentru acest lucru el va angaja un singur vanzator care va lucra un interval continuu de timp si care va fi platit cu o suma fixa $C$ pentru fiecare unitate de timp lucrata. Deasemenea el va avea de vanzare un singur tip de carnati pentru care vrea sa stabileasca un pret fix. Gigel stie ca prin fata magazinului sau trec $N$ oameni si pentru fiecare om cunoaste momentul de timp la care trece {$T{~i~}$} si pretul {$P{~i~}$} pe care este dispus sa il plateasca pentru un carnat(fiecare om {$i$} va cumpara un singur carnat daca {$P{~i~}$} este mai mic decat pretul fixat de Gigel).

Gigel vrea sa deschida un magazin de carnati. Pentru acest lucru el va angaja un singur vanzator care va lucra un interval continuu de timp si care va fi platit cu o suma fixa $C$ pentru fiecare unitate de timp lucrata. Deasemenea el va avea de vanzare un singur tip de carnati pentru care vrea sa stabileasca un pret fix. Gigel stie ca prin fata magazinului sau trec $N$ oameni si pentru fiecare om cunoaste momentul de timp la care trece {$T{~i~}$} si pretul {$P{~i~}$} pe care este dispus sa il plateasca pentru un carnat (fiecare om {$i$} va cumpara un singur carnat daca {$P{~i~}$} este mai mare sau egal decat pretul fixat de Gigel).

h2. Cerinta

Ajutati-l pe Gigel sa stabileasca intervalul de timp in care va fi deschis magazinul sau si pretul pe care il va fixa, pentru a maximiza profitul sau.

Ajutati-l pe Gigel sa stabileasca intervalul de timp in care va fi deschis magazinul si pretul pe care il va fixa, pentru a maximiza profitul sau.

h2. Date de intrare

h2. Restrictii
* {$1 ≤ N ≤ 2.000$}

* {$1 ≤ T{~i~} ≤ 1.500$}
* {$1 ≤ P{~i~} ≤ 1.000.000$}

* {$0 ≤ T{~i~} ≤ 1.500$}
* {$0 ≤ P{~i~} ≤ 1.000.000$}

* {$1 ≤ C ≤ 1.000.000$}
h2. Exemplu

h3. Explicatie

Magazinul va fi deschis de la {$8$} la {$19$}. Pretul fixat de el va fi {$129$}. Clientii {$2$}, {$4$} si {$5$} vor cumpara cate un carnat deci profitul sau va fi {$3*129-(19-8+1)*13=231$}.

Magazinul va fi deschis de la {$8$} la {$19$}. Pretul fixat de el va fi {$129$}. Clientii {$2$}, {$4$} si {$5$} vor cumpara cate un carnat. Vanzatorul va fi platit cu {$13*12=156$} deoarece lucreaza {$12$} unitati de timp. Profitul sau va fi {$3*129-12*13=231$}.

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

2715