HUGEKNAP - Cái túi ( Hard version )
Tác giả: ladpro98
Ngôn ngữ: Pascal
uses math;
var n, m, i, z, vv, t, tt, j: longint;
f: array[0..10005, 0..1005] of longint;
w, v, res: array[0..10005] of longint;
begin
read(t);
while (t > 0) do begin
read(n, m);
for i := 1 to n do read(w[i]);
for i := 1 to n do read(v[i]);
for i := 0 to m do f[0][i] := 0;
for i := 1 to n do
for j := 0 to m do begin
f[i][j] := f[i - 1][j];
if (j >= w[i]) then
f[i][j] := max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
end;
vv := f[n][m];
z := 0;
while (n <> 0) do begin
if (f[n][m] <> f[n - 1][m]) then begin
z := z + 1;
res[z] := n;
dec(m, w[n]);
end;
n := n - 1;
end;
writeln(vv, ' ' , z);
for i := 1 to z do write(res[i],' ');
writeln;
t := t - 1;
end;
end.