implicit none
integer(8),allocatable,dimension(:)::w,v
integer(8),allocatable,dimension(:,:)::dp
integer(8) n,w_sum,i,j,k,tmp

read(5,*) n,w_sum
allocate(w(n),v(n))
allocate(dp(0:n,0:w_sum))
dp(:,:)=0

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

do j=0,n-1
do k=0,w_sum
if(k-w(j).ge.0)then
tmp=w(j)
dp(j+1,k)=max(dp(j+1,k),dp(j,k-tmp)+v(j))
else
dp(j+1,k)=dp(j,k)
endif

enddo
enddo

write(6,*)dp(n,w_sum)

deallocate(w,v,dp)
end
