PROGRAM ATCODER

implicit none
integer(16) :: n, w_max, i, j, sum_w
integer(16), allocatable :: w(:), v(:), dp(:,:)

read(*,*) n, w_max
allocate(dp(n+1,w_max+1), w(n), v(n))

dp = 0

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

do i = 1, n
	do sum_w = 1, w_max+1
    	if (sum_w-w(i) > 0) then
        	call chmax(dp(i+1,sum_w), dp(i,sum_w-w(i))+v(i))
        end if
        call chmax(dp(i+1,sum_w), dp(i,sum_w))
    end do
end do

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

END PROGRAM ATCODER

subroutine chmax(dp,x)
implicit none
integer :: dp, x

if (dp < x) then
	dp = x
	return
end if

end subroutine