      PROGRAM Knapsack1
      IMPLICIT NONE
      integer(16) :: n,w
      integer(16),allocatable :: ww(:),vv(:),dp(:,:)
      integer(16) :: i,num,weight
      
      read*,n,w
      allocate( ww(n),vv(n),dp(0:n,0:w) )
      do i = 1,n
        read*,ww(i),vv(i)
      end do
      
      dp = 0
      do num = 1,n
        do weight = 1,w
          
          if( weight-ww(num)>=0 )then
            dp(num,weight) = max( dp(num-1,weight), &
              & dp(num-1,weight-ww(num))+vv(num) )
          else
            dp(num,weight) = dp(num-1,weight)
          end if
          
        end do
      end do
      
      print*,dp(n,w)
      
      
      
      
      END PROGRAM