Fişierul intrare/ieşire:peste.in, peste.outSursăpreONI 2008, Runda finala
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Peste

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 Pi pesti daca este lasata in apa cel putin Ti minute. Daca o plasa i este lasata mai mult de Ti minute in apa, ea nu va prinde mai mult peste, iar daca este lasata mai putin de Ti 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.

Date de intrare

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 Pi si Ti, reprezentand informatiile pentru plasa i.

Date de iesire

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.

Restrictii

  • 1 ≤ K, N, TTotal ≤ 50 000
  • 1 ≤ Pi, Ti ≤ 1000

Exemplu

peste.inpeste.out
3 2 5
10 5
2 4
1 3
12

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content