program main
integer N,sup_w!supはsupremum(上限)の略
integer,allocatable,dimension(:)::w,v
integer(16),allocatable,dimension(:,:)::DP
read*,N,sup_w
allocate(w(n),v(n))
allocate(DP(0:N,0:sup_w))
do i=1,n
  read*,w(i),v(i)
end do

DP=0
do i=1,N
  do j=0,sup_w
    if(j-w(i)>=0)then
      DP(i,j)=max(DP(i,j),DP(i-1,j-w(j))+v(i))
    else
      DP(i,j)=DP(i-1,j)
    end if
  end do
end do

print"(i0)",DP(N,sup_w)
end program main