program main
  implicit none
  integer :: i, j, Nmax, Wmax
  integer(16),allocatable,dimension(:) :: v, DP
  integer,allocatable,dimension(:) :: w
  read*, Nmax, Wmax
  allocate(v(Nmax), w(Nmax), DP(0:Wmax))

  do i = 1, Nmax
    read*, w(i), v(i)
  enddo

  DP = 0
  do i = 1, Nmax
    do j = Wmax, 0, -1
      if(j >= w(i))then
        DP(j) = max(DP(j - w(i)) + v(i), DP(j))
      endif
    enddo
  enddo
  print*, DP(Wmax)
end program