N=io.read"*n"
W=io.read"*n"
w,v={},{}for i=1,N do
w[i]=io.read"*n"
v[i]=io.read"*n"end

dp={[0]={}}
for i=0,W do dp[0][i]=0 end

for i=1,N do
dp[i]={}
for j=0,W do
if(j<w[i])then dp[i][j]=dp[i-1][j]
else dp[i][j]=math.max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])end
end
end
print(dp[N][W])