| Fişierul intrare/ieşire: | carnati.in, carnati.out | Sursă | preONI 2008, Runda 4 |
| Autor | Adrian Diaconu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | carnati.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.
