uses crt;
var f:text; n,m,i,j:longint; a,b,l1,l2,t:array[1..100]of longint;
begin
clrscr;
   assign(f,'Bag.inp');reset(f);
      readln(f,n,m);
      for i:=1 to n do readln(f,a[i],b[i]);   
   close(f);
   assign(f,'Bag.out');rewrite(f);
      l1[n]:=a[n]; l2[n]:=b[n]; 
      for i:=n downto 0 do
         begin
            l1[i]:=a[i]; l2[i]:=b[i];
            for j:=i+1 to n do
               if (a[i]+l1[j]<=m)and(b[i]+l2[j]>l2[i]) then
                  begin l1[i]:=l1[j]+a[i]; l2[i]:=l2[j]+b[i]; t[i]:=j; end;
         end;
      i:=t[0];
      writeln(f,l2[0]);
      while i<>0 do
         begin
            write(f,i,' ');
            i:=t[i];
         end;
   close(f); 
end.

Bài này mình dùng quy hoạch động, nó tương tự như bài dãy con có tổng lớn nhất nhưng thêm điều kiện tổng khối lượng các món hàng phải <m.

Có lỗi sai gì thì cứ góp ý nhé

Bảng phương án: