{Problema ruxacului dinamica
O persoana are la dispozitie un rucsac cu o capacitate de g unitati de
greutate si intentioneaza sa efectueze un transport in urma caruia sa obtina
un castig. Persoana are la dispozitie n obiecte, pentru fiecare se cunoaste
greutatea si castigul obtinut in urma transportului sau. Ce obiecte trebuie
sa transporte persoana pentru a-si maximiza castigul si care este acesta?}
program ruxac_dinamic;
type ruxac=record
    gr,c:integer;
end;
var v:array[1..100] of ruxac;
    castig,alege:array[0..100,0..100] of integer;
    n,g,i,j:integer;
    f,gg:text;

procedure citire;
var i:integer;
begin
     assign(f,'rucsac.in');
     reset(f);
     readln(f,n,g);
     {for i:=1 to n do
        read(f,v[i].gr);
     readln(f);
     for i:=1 to n do
        read(f,v[i].c);}
     for i:=1 to n do
        readln(f,v[i].gr,v[i].c);
     close(f);
end;

{castig[i,j] este max. dintre castig[i-1,j] si castig[i-1,j-v[i].gr]+v[i].c}
procedure dinamica;
var i,j:integer;
begin
    for i:=1 to n do
      for j:=1 to g do
       if (v[i].gr<=j) and (castig[i-1,j-v[i].gr]+v[i].c>castig[i-1,j]) then
          begin
              castig[i,j]:=castig[i-1,j-v[i].gr]+v[i].c;
              alege[i,j]:=i;
          end
            else
             begin
                castig[i,j]:=castig[i-1,j];
                alege[i,j]:=alege[i-1,j];
             end;
end;

{procedure afisare(i,j:integer);
begin
     if alege[i,j]<>0 then
        begin
          if alege[i,j]<>alege[i-1,j-v[alege[i,j]].gr] then
           begin
           afisare(i-1,j-v[alege[i,j]].gr);
           write(gg,alege[i,j],' ');
           end
             else afisare(i-1,j);
        end;
end;
     }
begin
        citire;
        assign(gg,'rucsac.out');
        rewrite(gg);
        dinamica;
        writeln(gg,castig[n,g]);
       { afisare(n,g); }
        close(gg);
end.