Fişierul intrare/ieşire:carnati.in, carnati.outSursăpreONI 2008, Runda 4
AutorAdrian DiaconuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 Ti si pretul Pi pe care este dispus sa il plateasca pentru un carnat (fiecare om i va cumpara un singur carnat daca Pi este mai mare sau egal decat pretul fixat de Gigel).

Cerinta

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.

Date de intrare

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 Ti si Pi.

Date de iesire

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

Restrictii

  • 1 ≤ N ≤ 2.000
  • 0 ≤ Ti ≤ 1.500
  • 0 ≤ Pi ≤ 1.000.000
  • 1 ≤ C ≤ 1.000.000

Exemplu

carnati.incarnati.out
8 13
2 115
8 157
11 56
15 129
19 158
35 137
50 116
59 129
231

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. Vanzatorul va fi platit cu 13*12=156 deoarece lucreaza 12 unitati de timp. Profitul sau va fi 3*129-12*13=231.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content