program main
  implicit none

  integer(8), allocatable :: wv(:,:), dp(:,:)
  integer(8) :: n, wmax, i, j

  read(*,*) n, wmax

  allocate(wv(2,n))
  allocate(dp(n,wmax))

  read(*,*) wv

  do i = 1, n
     do j = 1, wmax
        dp(i,j) = -1
     end do
  end do

  do j = 1, wmax
     if(j - wv(1,1) >= 0) then
        dp(1,j) = wv(2,1)
     else
        dp(1,j) = 0
     end if
  end do
     
  
  do j = 1, wmax
     do i = 2, n
        if(j - wv(1,i) >= 0) then
           if(j - wv(1,i) == 0) then
              dp(i,j) = max(dp(i,j), 0 + wv(2,i))
           else
              dp(i,j) = max(dp(i,j), dp(i-1,j-wv(1,i)) + wv(2,i))
           end if
        end if
        
        dp(i,j) = max(dp(i,j), dp(i-1, j))
     end do
  end do

  write(*,*) dp(n,wmax)

end program main

           
  
  
  
