program EDPCD
    implicit none
    integer(8)::N,W,i,j
    integer(8),dimension(100)::wi,vi
    integer(8),dimension(100000,100)::dp
    read(5,*)N,W
    read(5,*)(wi(i),vi(i),i=1,N)
    dp=0

    do i=1,N
        do j=1,W
            if(i==1)then
                if(j>=wi(i))then
                    dp(j,i)=vi(i)
                end if
            else if(j<wi(i))then
                dp(j,i)=dp(j,i-1)
            else if(j==wi(i))then
                dp(j,i)=max(dp(j,i-1),vi(i))
            else
                dp(j,i)=max(dp(j,i-1),dp(j-wi(i),i-1)+vi(i))
            end if
        end do
    end do

    print'(i0)',dp(W,N)
end program EDPCD