program knapsack1
  implicit none
  integer :: n, w, wi, i
  integer(8) :: vi, dp0(0:100000), dp1(0:100000)
  dp0 = 0_8
  dp1 = 0_8
  read(*,*) n, w
  do i = 1, n
    read(*,*) wi, vi
    dp1(0:wi-1) = dp0(0:wi-1)
    dp1(wi:w) = max(dp0(wi:w),dp0(0:w-wi)+vi)
    dp0(0:w) = dp1(0:w)
  end do
  write(*,'(i0)') dp0(w)
  stop
end program knapsack1