## Editorial for Cái túi 1

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
fo='';
maxn=40;
maxc=1048575;
var n,re,m,mid,max,num:longint;
v,w:array[1..40] of longint;
f,g:array[0..maxc] of longint;

procedure rf;
var i:longint;
begin
for i:=1 to n do read(w[i],v[i]);
end;

procedure calc;
var i,j:longint;
begin
max:=1 shl mid-1;
for i:=1 to max do
for j:=0 to mid-1 do
if (i shr j) and 1=1 then
begin
f[i]:=f[i]+w[j+1];
g[i]:=g[i]+v[j+1];
end;
end;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
i:=l; j:=r; x:=f[(i+j) shr 1]; y:=g[(i+j) shr 1];
repeat
while (f[i]<x) or ((f[i]=x) and (g[i]>y)) do i:=i+1;
while (f[j]>x) or ((f[j]=x) and (g[j]<y)) do j:=j-1;
if i<=j then
begin
t:=f[i]; f[i]:=f[j]; f[j]:=t;
t:=g[i]; g[i]:=g[j]; g[j]:=t;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

procedure edit;
var i:longint;
begin
num:=0;
for i:=1 to max do
if g[i]>g[num] then
begin
num:=num+1;
f[num]:=f[i];
g[num]:=g[i];
end;
end;

function bs(t:longint):longint;
var l,r,md,i:longint;
begin
l:=0; r:=num;
while l<=r do
begin
md:=(l+r) shr 1;
if f[md]=t then break;
if f[md]<t then l:=md+1
else r:=md-1;
end;
if f[md]=t then bs:=md
else
begin
for i:=md+1 downto md-1 do
if (i>=0) and (i<=num) and (f[i]<=t) then
begin
bs:=i; exit;
end;
end;
end;

procedure pr;
var i,l,ww,vv,j,x:longint;
begin
mid:=(n+1) shr 1;
calc;
sort(1,max);
edit;
l:=mid+1; mid:=n-mid;
max:=1 shl mid-1;
re:=0;
for i:=0 to max do
begin
ww:=0; vv:=0;
for j:=0 to mid-1 do
if (i shr j) and 1=1 then
begin
ww:=ww+w[l+j];
vv:=vv+v[l+j];
end;
if ww<=m then
begin
x:=bs(m-ww);
if vv+g[x]>re then re:=vv+g[x];
end;
end;
end;

procedure wf;
begin
writeln(re);
end;

begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
rf;
pr;
wf;
close(input); close(output);
end.


#### Code mẫu của RR

{\$MODE OBJFPC}

uses math;
const
FINP          =       '';
FOUT          =       '';
MAXN          =       40;

var
f1,f2         :       text;
n,m           :       longint;
res           :       int64;
v,w           :       array[1..MAXN] of longint;

n1,n2         :       longint;
sv1,sv2,
sw1,sw2       :       array[0..1050000] of longint;

procedure inp;
var
i:longint;
begin
for i:=1 to n do
end;

procedure swap(var a,b:longint); inline;
var
tmp:longint;
begin
tmp:=a; a:=b; b:=tmp;
end;

procedure sort1(l,r:longint); inline;
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=sw1[l+random(r-l+1)];
repeat
while sw1[i]<mid do inc(i);
while sw1[j]>mid do dec(j);
if i<=j then
begin
swap(sv1[i],sv1[j]);
swap(sw1[i],sw1[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort1(i,r);
if l<j then sort1(l,j);
end;

procedure sort2(l,r:longint); inline;
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=sw2[l+random(r-l+1)];
repeat
while sw2[i]<mid do inc(i);
while sw2[j]>mid do dec(j);
if i<=j then
begin
swap(sv2[i],sv2[j]);
swap(sw2[i],sw2[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort2(i,r);
if l<j then sort2(l,j);
end;

procedure solve;
var
i,j,bit,nn,m1:longint;
begin
nn:=n shr 1;
n1:=1 shl nn;
n2:=1 shl (n-nn);

for i:=0 to n1-1 do
for bit:=1 to nn do
if (i shr (bit-1)) and 1=1 then
begin
inc(sv1[i],v[bit]);
inc(sw1[i],w[bit]);
end;

for i:=0 to n2-1 do
for bit:=1 to n-nn do
if (i shr (bit-1)) and 1=1 then
begin
inc(sv2[i],v[bit+nn]);
inc(sw2[i],w[bit+nn]);
end;

sort1(0,n1-1);
sort2(0,n2-1);

j:=0; res:=0; m1:=sv1[j];
for i:=n2-1 downto 0 do
begin
while (j<n1-1) and (sw1[j+1]+sw2[i]<=m) do
begin
inc(j);
m1:=max(m1,sv1[j]);
end;
if (sw1[j]+sw2[i]<=m) and (m1+sv2[i]>res) then res:=m1+sv2[i];
end;
writeln(f2,res);
end;

begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
inp;
solve;
close(f1); close(f2);
end.