Program DTtui1;
CONST
fin='';
fon='';
maxn=40;
maxth=1048576;
Type
Opt=Record
kl,gt:longint; //Khoi luong, Gia tri
End;
ToHop=array [1..maxth] of Opt;
Var
o:array [1..2] of ToHop;
dem:array [1..2] of longint;
amax:array [1..maxth] of longint;
w,v:array [1..maxn] of longint; //Weight, Value
m,i,j,sw,sv,sum:longint;
n,mid:byte;
f:text;
//--------------------------------------------------
Procedure Nhap;
Var i:byte;
Begin
Assign(f,fin);
Reset(f);
Readln(f,n,m);
For i:=1 to n do
Readln(f,w[i],v[i]);
Close(f);
ENd;
//------------------------------------------
Procedure Sort(l,r:longint);
Var i,j,x:longint;
y:Opt;
Begin
i:=l;
j:=r;
x:=o[2,l+random(r-l+1)].kl;
Repeat
While o[2,i].kl<x Do inc(i);
While o[2,j].kl>x do dec(j);
If not(i>j) Then
Begin
y:=o[2,i];
o[2,i]:=o[2,j];
o[2,j]:=y;
inc(i);
dec(j);
ENd;
Until i>j;
If i<r Then sort(i,r);
If l<j Then sort(l,j);
End;
//-----------------------------------------
Procedure Luu(x:byte);
Var k:longint;
Begin
inc(dem[x]);
k:=dem[x];
o[x,k].kl:=sw;
o[x,k].gt:=sv;
End;
//----------------------------------------
Procedure Duyet(bit,i,k:byte);
Var j:byte;
Begin
If sw>m Then Exit;
For j:=0 to 1 do
Begin
sw:=sw+j*w[i];
sv:=sv+j*v[i];
If i=k Then
Begin
If sw<=m Then Luu(bit);
End
else Duyet(bit,i+1,k);
sw:=sw-j*w[i];
sv:=sv-j*v[i];
End;
End;
//-------------------------------------
Procedure CheckMax;
Var i,max:longint;
Begin
amax[1]:=1;
max:=1;
For i:=2 to dem[2] do
Begin
If o[2,i].gt>o[2,max].gt Then max:=i;
amax[i]:=max;
End;
End;
//-----------------------------------
Function Find(bit:byte; x:longint):longint;
Var dau,giua,cuoi:longint;
Begin
dau:=1;
cuoi:=dem[bit]+1;
Repeat
giua:=(dau+cuoi) div 2;
If o[bit,giua].kl <= x Then dau:=giua
else cuoi:=giua;
Until dau+1=cuoi;
Exit(dau);
End;
//------------------------------------
Procedure Xuat;
Begin
Assign(f,fon);
Rewrite(f);
Writeln(f,sum);
Close(f);
End;
Begin
Randomize;
Nhap;
mid:=n div 2;
Duyet(1,1,mid);
Duyet(2,mid+1,n);
sort(1,dem[2]);
CheckMax;
For i:=1 to dem[1] do
Begin
j:=Find(2,m-o[1,i].kl);
If o[1,i].gt + o[2,amax[j]].gt > sum Then sum:=o[1,i].gt + o[2,amax[j]].gt;
End;
Xuat;
End.
UHJvZ3JhbSBEVHR1aTE7CkNPTlNUCiAgICAgICAgZmluPScnOwogICAgICAgIGZvbj0nJzsKICAgICAgICBtYXhuPTQwOwogICAgICAgIG1heHRoPTEwNDg1NzY7ClR5cGUKICAgICAgICBPcHQ9UmVjb3JkCiAgICAgICAgICAgICAgICBrbCxndDpsb25naW50OyAgICAgICAgICAvL0tob2kgbHVvbmcsIEdpYSB0cmkKICAgICAgICBFbmQ7CiAgICAgICAgVG9Ib3A9YXJyYXkgWzEuLm1heHRoXSBvZiBPcHQ7ClZhcgogICAgICAgIG86YXJyYXkgWzEuLjJdIG9mIFRvSG9wOwogICAgICAgIGRlbTphcnJheSBbMS4uMl0gb2YgbG9uZ2ludDsKICAgICAgICBhbWF4OmFycmF5IFsxLi5tYXh0aF0gb2YgbG9uZ2ludDsKICAgICAgICB3LHY6YXJyYXkgWzEuLm1heG5dIG9mIGxvbmdpbnQ7ICAgLy9XZWlnaHQsIFZhbHVlCiAgICAgICAgbSxpLGosc3csc3Ysc3VtOmxvbmdpbnQ7CiAgICAgICAgbixtaWQ6Ynl0ZTsKICAgICAgICBmOnRleHQ7Ci8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KICAgICAgICBQcm9jZWR1cmUgTmhhcDsKICAgICAgICBWYXIgaTpieXRlOwogICAgICAgIEJlZ2luCiAgICAgICAgICAgICAgICBBc3NpZ24oZixmaW4pOwogICAgICAgICAgICAgICAgUmVzZXQoZik7CiAgICAgICAgICAgICAgICBSZWFkbG4oZixuLG0pOwogICAgICAgICAgICAgICAgRm9yIGk6PTEgdG8gbiBkbwogICAgICAgICAgICAgICAgICAgICAgICBSZWFkbG4oZix3W2ldLHZbaV0pOwogICAgICAgICAgICAgICAgQ2xvc2UoZik7CiAgICAgICAgRU5kOwogICAgICAgIC8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiAKICAgICAgICAgICAgICAgIFByb2NlZHVyZSBTb3J0KGwscjpsb25naW50KTsKICAgICAgICAgICAgICAgIFZhciBpLGoseDpsb25naW50OwogICAgICAgICAgICAgICAgICAgICAgICB5Ok9wdDsKICAgICAgICAgICAgICAgIEJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgIGk6PWw7CiAgICAgICAgICAgICAgICAgICAgICAgIGo6PXI7CiAgICAgICAgICAgICAgICAgICAgICAgIHg6PW9bMixsK3JhbmRvbShyLWwrMSldLmtsOwogICAgICAgICAgICAgICAgICAgICAgICBSZXBlYXQKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBXaGlsZSBvWzIsaV0ua2w8eCBEbyBpbmMoaSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgV2hpbGUgb1syLGpdLmtsPnggZG8gZGVjKGopOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIElmIG5vdChpPmopIFRoZW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5Oj1vWzIsaV07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBvWzIsaV06PW9bMixqXTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG9bMixqXTo9eTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluYyhpKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRlYyhqKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEVOZDsKICAgICAgICAgICAgICAgICAgICAgICAgVW50aWwgaT5qOwogICAgICAgICAgICAgICAgICAgICAgICBJZiBpPHIgVGhlbiBzb3J0KGkscik7CiAgICAgICAgICAgICAgICAgICAgICAgIElmIGw8aiBUaGVuIHNvcnQobCxqKTsKICAgICAgICAgICAgICAgIEVuZDsKICAgICAgICAvLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiAgICAgICAgUHJvY2VkdXJlIEx1dSh4OmJ5dGUpOwogICAgICAgIFZhciBrOmxvbmdpbnQ7CiAgICAgICAgQmVnaW4KICAgICAgICAgICAgICAgIGluYyhkZW1beF0pOwogICAgICAgICAgICAgICAgazo9ZGVtW3hdOwogICAgICAgICAgICAgICAgb1t4LGtdLmtsOj1zdzsKICAgICAgICAgICAgICAgIG9beCxrXS5ndDo9c3Y7CiAgICAgICAgRW5kOwogICAgICAgIC8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQogICAgICAgIFByb2NlZHVyZSBEdXlldChiaXQsaSxrOmJ5dGUpOwogICAgICAgIFZhciBqOmJ5dGU7CiAgICAgICAgQmVnaW4KICAgICAgICAgICAgICAgIElmIHN3Pm0gVGhlbiBFeGl0OwogICAgICAgICAgICAgICAgRm9yIGo6PTAgdG8gMSBkbwogICAgICAgICAgICAgICAgICAgICAgICBCZWdpbgogICAgICAgICAgICAgICAgICAgICAgICBzdzo9c3craip3W2ldOwogICAgICAgICAgICAgICAgICAgICAgICBzdjo9c3Yraip2W2ldOwogICAgICAgICAgICAgICAgICAgICAgICBJZiBpPWsgVGhlbgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgSWYgc3c8PW0gVGhlbiBMdXUoYml0KTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBFbmQKICAgICAgICAgICAgICAgICAgICAgICAgZWxzZSBEdXlldChiaXQsaSsxLGspOwogICAgICAgICAgICAgICAgICAgICAgICBzdzo9c3ctaip3W2ldOwogICAgICAgICAgICAgICAgICAgICAgICBzdjo9c3Ytaip2W2ldOwogICAgICAgICAgICAgICAgICAgICAgICBFbmQ7CiAgICAgICAgRW5kOwogICAgICAgIC8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQogICAgICAgIFByb2NlZHVyZSBDaGVja01heDsKICAgICAgICBWYXIgaSxtYXg6bG9uZ2ludDsKICAgICAgICBCZWdpbgogICAgICAgICAgICAgICAgYW1heFsxXTo9MTsKICAgICAgICAgICAgICAgIG1heDo9MTsKICAgICAgICAgICAgICAgIEZvciBpOj0yIHRvIGRlbVsyXSBkbwogICAgICAgICAgICAgICAgICAgICAgICBCZWdpbgogICAgICAgICAgICAgICAgICAgICAgICBJZiBvWzIsaV0uZ3Q+b1syLG1heF0uZ3QgVGhlbiBtYXg6PWk7CiAgICAgICAgICAgICAgICAgICAgICAgIGFtYXhbaV06PW1heDsKICAgICAgICAgICAgICAgICAgICAgICAgRW5kOwogICAgICAgIEVuZDsKICAgICAgICAvLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiAgICAgICAgRnVuY3Rpb24gRmluZChiaXQ6Ynl0ZTsgeDpsb25naW50KTpsb25naW50OwogICAgICAgIFZhciBkYXUsZ2l1YSxjdW9pOmxvbmdpbnQ7CiAgICAgICAgQmVnaW4KICAgICAgICAgICAgICAgIGRhdTo9MTsKICAgICAgICAgICAgICAgIGN1b2k6PWRlbVtiaXRdKzE7CiAgICAgICAgICAgICAgICBSZXBlYXQKICAgICAgICAgICAgICAgICAgICAgICAgZ2l1YTo9KGRhdStjdW9pKSBkaXYgMjsKICAgICAgICAgICAgICAgICAgICAgICAgSWYgb1tiaXQsZ2l1YV0ua2wgPD0geCBUaGVuIGRhdTo9Z2l1YQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlIGN1b2k6PWdpdWE7CiAgICAgICAgICAgICAgICBVbnRpbCBkYXUrMT1jdW9pOwogICAgICAgICAgICAgICAgRXhpdChkYXUpOwogICAgICAgIEVuZDsKICAgICAgICAvLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQogICAgICAgIFByb2NlZHVyZSBYdWF0OwogICAgICAgIEJlZ2luCiAgICAgICAgICAgICAgICBBc3NpZ24oZixmb24pOwogICAgICAgICAgICAgICAgUmV3cml0ZShmKTsKICAgICAgICAgICAgICAgIFdyaXRlbG4oZixzdW0pOwogICAgICAgICAgICAgICAgQ2xvc2UoZik7CiAgICAgICAgRW5kOwpCZWdpbgogICAgICAgIFJhbmRvbWl6ZTsKICAgICAgICBOaGFwOwogICAgICAgIG1pZDo9biBkaXYgMjsKICAgICAgICBEdXlldCgxLDEsbWlkKTsKICAgICAgICBEdXlldCgyLG1pZCsxLG4pOwogICAgICAgIHNvcnQoMSxkZW1bMl0pOwogICAgICAgIENoZWNrTWF4OwogCiAgICAgICAgRm9yIGk6PTEgdG8gZGVtWzFdIGRvCiAgICAgICAgICAgICAgICBCZWdpbgogICAgICAgICAgICAgICAgajo9RmluZCgyLG0tb1sxLGldLmtsKTsKICAgICAgICAgICAgICAgIElmIG9bMSxpXS5ndCArIG9bMixhbWF4W2pdXS5ndCA+IHN1bSBUaGVuIHN1bTo9b1sxLGldLmd0ICsgb1syLGFtYXhbal1dLmd0OwogICAgICAgICAgICAgICAgRW5kOwogICAgICAgIFh1YXQ7CkVuZC4=