program ddd
implicit none

integer(8) :: n, w, i, j
integer(8),allocatable,dimension(:) :: g, v, dp

read*, n, w
allocate(g(n))
allocate(v(n))
allocate(dp(0:w))
do i=1,n
read*, g(i), v(i)
end do
dp=0

do j=1, n
 do i=0,w
 if(i>=g(j)) then
 dp(i)=max(dp(i),dp(i-g(j))+v(j))
 end if
 end do
end do

write(*,'(i0)') dp(w)

end program
