== include(page="template/taskheader" task_id="peste") ==
Poveste si cerinta...
Titus merge la pescuit pe malul raului Bahlui, unde isi propune sa stea $TTotal$ minute. El detine $N$ plase de prins peste si fiecare plasa $i$ poate prinde $P{~i~}$ pesti daca este lasata in apa cel putin $T{~i~}$ minute. Daca o plasa $i$ este lasata mai mult de $T{~i~}$ minute in apa, ea nu va prinde mai mult peste, iar daca este lasata mai putin de $T{~i~}$ minute nu va prinde peste deloc. De asemenea, niciodata in apa nu pot fi mai mult de $K$ plase de prins peste. Astfel, Titus incepe pescuitul la momentul de timp $0$ (zero) si in orice moment de timp poate face una din urmatoarele actiuni:
* Introduce o plasa de prins peste in apa, numai daca in apa nu sunt deja $K$ plase de prins peste si plasa pe care vrea s-o introduca nu se afla deja in apa
* Scoate o plasa din apa si colecteaza pestii aflati in ea, numai daca toate plasele care sunt in apa au terminat de prins peste (altfel pestii se vor speria si nu va mai prinde nimic)
Cosideram ca ambele actiuni se realizeaza instantaneu (nu consuma nicio unitate de timp), deci la un moment de timp Titus poate realiza oricare din cele doua actiuni de mai multe ori. Aflati pentru Titus care este numarul maxim de pesti pe care il poate prinde in $TTotal$ minute.
h2. Date de intrare
Fisierul de intrare $peste.in$ ...
Fisierul de intrare $peste.in$ contine pe prima linie, separate printr-un spatiu, numerele naturale $N$, $K$ si $TTotal$, avand semnificatia din enunt. Pe urmatoarele $N$ linii se afla informatii despre plasele de prins peste, pe linia $i+1$ aflandu-se $P{~i~}$ si $T{~i~}$, reprezentand informatiile pentru plasa $i$.
h2. Date de iesire
In fisierul de iesire $peste.out$ ...
In fisierul de iesire $peste.out$ se afla pe prima linie numarul natural $Res$, reprezentand numarul maxim de pesti pe care Titus ii poate prinde in $TTotal$ minute.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ K, N, TTotal ≤ 50 000$
* $1 ≤ P{~i~}, T{~i~} ≤ 1000$
h2. Exemplu
table(example). |_. peste.in |_. peste.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 2 5
10 5
2 4
1 3
| 12
|
h3. Explicatie
...
O solutie posibila e urmatoarea: la momentul $0$ introduce prima plasa, la momentul $1$ introduce a doua plasa, la momentul $5$ ambele plase au terminat de prins peste, deci poate scoate intai prima plasa, colecteaza pestii din ea, apoi face acelasi lucru pentru a doua plasa (amintim ca aceste actiuni se realizeaza instant), prinzand in total $12$ pesti.
== include(page="template/taskfooter" task_id="peste") ==
