PROGRAM INFOARENA_ENERGII;
(*
  Ideea de rezolvare este asemanatoare cu "Problema discreta a rucsacului".
Adica, se foloseste METODA PROGRAMARII DINAMICE!
Folosesc vectorii:
    - Ci[j]= costul minim pentru repornirea centralei, astfel incat sa se
             poata produce o cantitate de energie MAI MARE SAU EGALA cu "j",
             avand la dispozitie primele "i" generatoare.
    - Ci_1[j]= costul minim pentru repornirea centralei, astfel incat sa se
             poata produce o cantitate de energie MAI MARE SAU EGALA cu "j",
             avand la dispozitie primele "i-1" generatoare.
*)
CONST Gmax=1000;  {Gmax= nr. maxim de generatoare}
      Wmax=5000;  {Wmax= cant. max. de energie necesara repornirii centralei}
      INFINIT=MAXLONGINT DIV 2;
VAR EG,CG:ARRAY[1..Gmax] OF WORD;
    Ci,Ci_1:ARRAY[0..Wmax] OF LONGINT;
    G,I:0..Gmax;
    W,J:0..Wmax;
    C1,C2:LONGINT;
    F1,F2:TEXT;
BEGIN
ASSIGN(F1,'energii.in');
ASSIGN(F2,'energii.out');
RESET(F1);
REWRITE(F2);
READLN(F1,G);
READLN(F1,W);
FOR I:=1 TO G DO READLN(F1,EG[I],CG[I]);

{Initializez "linia zero" (costul minim folosind "zero" generatoare)!}
Ci[0]:=0;
FOR J:=1 TO W DO Ci[J]:=INFINIT;

{PROGRAMARE DINAMICA!}
FOR I:=1 TO G DO
    BEGIN
    Ci_1:=Ci;
    FOR J:=1 TO W DO
        IF (J>=EG[I]) THEN BEGIN
                           C1:=Ci_1[J];
                           C2:=Ci_1[J-EG[I]]+CG[I];
                           IF (C2<C1) THEN Ci[J]:=C2
                                      {ELSE Ci[J]:=C1;}
                           END
                      ELSE IF (CG[I]<Ci_1[J]) THEN Ci[J]:=CG[I]
                                              {ELSE Ci[J]:=Ci_1[J];}
    END;

{Scriu solutia, daca exista!}
IF (Ci[W]<INFINIT) THEN WRITE(F2,Ci[W])
                   ELSE WRITE(F2,-1);
CLOSE(F1);
CLOSE(F2);
END.