program Knapsack_1
    implicit none
    integer(4):: n,wn
    integer(8), allocatable:: w(:), v(:)
    integer(8), allocatable:: dp(:), ndp(:)
    integer(4):: i, j

    read*, n, wn
    allocate(w(n), v(n), dp(0:wn), ndp(0:wn))
    do i=1, n
        read*, w(i), v(i)
    end do

    dp(:) = 0
    ndp(:) = 0

    do i=1,n
        do j=1, wn
            if (j < w(i)) then
                ndp(j) = dp(j)
            else
                ndp(j) = max(dp(j), dp(j-w(i)) + v(i))
            end if
        end do
        dp(:) = ndp(:)
    end do

    print*, dp(wn)
end program Knapsack_1