==Include(page="template/taskheader" task_id="lapte")==
EU FAC ASTA!
Lapte
Haralambie este un mare bautor de lapte. Impreuna cu prietenii sai organizeaza adesea petreceri salbatice, in care se intrec in bautul laptelui. De data aceasta ei au organizat un joc. Ei au doua feluri de lapte : lapte A si lapte B. In aceasta noapte si-au propus sa bea cel putin L litri din fiecare fel. Dar mai e putin si se face dimineata, parintii lui Haralambie se intorc acasa si petrecerea se sparge. Ajutati-i sa bea cat mai repede.
Haralambie este un mare bautor de lapte. Impreuna cu prietenii sai organizeaza adesea petreceri salbatice, in care se intrec in bautul laptelui. De data aceasta ei au organizat un joc. Ei au doua feluri de lapte : $lapte A$ si $lapte B$. In aceasta noapte si-au propus sa bea cel putin $L$ litri din fiecare fel. Dar mai e putin si se face dimineata, parintii lui Haralambie se intorc acasa si petrecerea se sparge. Ajutati-i sa bea cat mai repede.
h2. Cerinta
Se cunoaste viteza cu care fiecare persoana bea un litru din laptele A si laptele B. Trebuie planificata o strategie astfel incat la sfarsitul petrecerii sa fi baut cel putin L litri din laptele A si cel putin L litri din laptele B, iar timpul total sa fie minim. O persoana nu poate bea din doua tipuri de lapte in acelasi timp.
Se cunoaste viteza cu care fiecare persoana bea un litru din $laptele A$ si $laptele B$. Trebuie planificata o strategie astfel incat la sfarsitul petrecerii sa fi baut cel putin $L$ litri din $laptele A$ si cel putin $L$ litri din $laptele B$, iar timpul total sa fie minim. O persoana nu poate bea din doua tipuri de lapte in acelasi timp.
h2. Date de Intrare
h2. Date de intrare
Pe prima linie a fisierului de intrare lapte.in sunt scrise numerele N (numarul persoane participante) si L (cantitatea minima de lapte ce trebuie bauta pana la sfarsitul petrecerii). Pe urmatoarele N linii sunt date perechi de numere naturale nenule a b (1<=a,b<=100) reprezentand timpul in care persoana corespunzatoare bea 1 litru de lapte A, respectiv timpul in care bea 1 litru de lapte B.
Pe prima linie a fisierului de intrare $lapte.in$ sunt scrise numerele $N$ (numarul persoane participante) si $L$ (cantitatea minima de lapte ce trebuie bauta pana la sfarsitul petrecerii). Pe urmatoarele $N$ linii sunt date perechi de numere naturale nenule $a b (1 ≤ a, b ≤ 100)$ reprezentand timpul in care persoana corespunzatoare bea $1$ litru de $lapte A$, respectiv timpul in care bea $1$ litru de $lapte B$.
h2. Date de Iesire
h2. Date de iesire
Prima linie a fisierului lapte.out va contine un singur numar T - timpul minim in care se va bea cantitatea ceruta de lapte. Pe urmatoarele N linii vor fi perechi de numere naturale. Linia i+1 va contine numerele x y , reprezentand cantitatea de lapte A, respectiv cantitatea de lapte B pe care o bea persoana i.
Prima linie a fisierului $lapte.out$ va contine un singur numar $T$ - timpul minim in care se va bea cantitatea ceruta de lapte. Pe urmatoarele $N$ linii vor fi perechi de numere naturale. Linia $i + 1$ va contine numerele $x y$ , reprezentand cantitatea de $lapte A$, respectiv cantitatea de $lapte B$ pe care o bea persoana $i$.
h2. Restrictii si precizari
S 1 <= N, T, L <= 100
S Cantitatea de lapte disponibila se considera nelimitata
S Consumul excesiv de lapte duce la epuizarea bauturii
* $1 ≤ N, T, L ≤ 100$
* Cantitatea de lapte disponibila se considera nelimitata
* Consumul excesiv de lapte duce la epuizarea bauturii
h2. Exemplu
lapte.in lapte.out Explicatii
3 20 18 Timpul minim este 18. Cantitatea de lapte A bauta este 0+5+18=23, cantitatea de lapte B bauta este 18+2=20.
1 1 0 18 Persoana 1 termina de baut in 1*0+1*18=18 minute.
2 4 5 2 Persoana 2 termina in 2*5+4*2=18 minute.
1 6 18 0 Persoana 3 termina in 1*18+6*0=18 minute.
Timpul minim dupa care petrecerea va lua sfarsit este max(18,18,18)=18
table(example). |_. lapte.in |_. lapte.out |
| 3 20
1 1
2 4
1 6
| 18
0 18
5 2
18 0 |
h3. Explicatii
Timpul minim este $18$.
Cantitatea de lapte $A$ bauta este $0+5+18=23$.
Cantitatea de lapte $B$ bauta este $18+2=20$.
Persoana $1$ termina de baut in $1*0+1*18=18$ minute.
Persoana $2$ termina in $2*5+4*2=18$ minute.
Persoana $3$ termina in $1*18+6*0=18$ minute.
Timpul minim dupa care petrecerea va lua sfarsit este $max(18,18,18)=18$
==Include(page="template/taskfooter" task_id="lapte")==
