procesor

Procesor

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

Poveste şi cerinţă...

Aveti la dispozitie un procesor si $N$ procese care trebuie executate pe acest procesor. Timpul de rulare al fiecarui proces este de exact o secunda, iar procesorul poate executa maxim un singur proces in orice moment de timp. Incepand de la momentul de timp zero, voi trebuie sa decideti ce procese vor rula pe procesor si la ce momente de timp. Daca un proces $i$ isi va incepe executia mai tarziu de timpul $T{~i~}$ (la un moment de timp cu o valoare mai mare sau egala decat $T{~i~}$), atunci va fi aplicata o penalizare $P{~i~}$. Voi trebuie sa calculati penalizarea totala minima posibila.

h2. Date de intrare

Fişierul de intrare $procesor.in$ ...

Fişierul de intrare $procesor.in$ va contine pe prima linie numarul natural $N$, avand semnificatia din enunt. Urmeaza apoi $N$ linii, pe linia $i+1$ aflandu-se, separate de un singur spatiu, doua valori $T{~i~}$ si $P{~i~}$.

h2. Date de ieşire

În fişierul de ieşire $procesor.out$ ...

În fişierul de ieşire $procesor.out$ se va afla o singura valoare, penalizarea totala minima posibila.

h2. Restricţii

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

* $1 ≤ N ≤ 100 000$
* $1 ≤ T{~i~} ≤ 1 000 000$
* $1 ≤ P{~i~} ≤ 1 000 000 000$

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

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

| 3
  1 10
  1 5
  4 4
| 5

|
h3. Explicaţie

...

O solutie posibila este urmatoarea: la momentul de timp $0$ incepe executia primul proces. Apoi la momentul de timp $1$ isi incepe executia al treilea proces. La momentul de timp $2$ incepe executia al doilea proces, pentru care se aplica o penalizare egala cu $5$.

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

5301