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

Poveste si cerinta...

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).
 
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.

h2. Date de intrare

Fisierul de intrare $carnati.in$ ...

Fisierul de intrare $carnati.in$ va contine pe prima linie doua numere intregi {$N$} si {$C$}. Pe urmatoarele {$N$} linii se vor afla cate 2 numere intregi {$T{~i~}$} si {$P{~i~}$}.

h2. Date de iesire

In fisierul de iesire $carnati.out$ ...

In fisierul de iesire $carnati.out$ se va afla un singur numar, profitul maxim pe care il poate obtine Gigel.

h2. Restrictii

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

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

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

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

| 8 13
2 115
8 157
11 56
15 129
19 158
35 137
50 116
59 129
| 231

|
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$}.
 

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