program ddd
implicit none

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

read*, n, w

allocate(g(n))
allocate(v(n))
allocate(dp(0:w,0:n))
dp=0

do i=1,n
read*, g(i), v(i)
end do

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

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

end program