program all_you_can_eat
    implicit none
    integer(4):: n, t
    integer(4),allocatable:: a(:), b(:)
    integer(4):: i,j,k, max_sat, ans
    integer(4),allocatable:: dp(:,:),old_dp(:,:)
    logical:: update = .true.
    logical, allocatable:: eated(:,:), old_eated(:,:)

    read*, n,t
    allocate(a(n), b(n))
    do i=1, n
        read*, a(i), b(i)
    end do
    max_sat = sum(b(:))
    allocate(dp(2,0:max_sat), old_dp(2,0:max_sat), source=t+1000)
    allocate(eated(n,0:max_sat),old_eated(n,0:max_sat), source=.false.)
    dp(:,0) = 0

    do while (update)
        update = .false.
        old_dp(:,:) = dp(:,:)
        old_eated(:,:) = eated(:,:)
        do i=0, max_sat
            do j=1, n
                if(eated(j,i)) cycle
                if (old_dp(2,i)+a(j) <= old_dp(2,i+b(j))) then
                    dp(2,i+b(j)) = old_dp(2,i)+a(j)
                    if (old_dp(2,i) < old_dp(1,i+b(j))) then
                        dp(1,i+b(j)) = old_dp(2,i)
                        eated(:, i+b(j)) = old_eated(:, i)
                        eated(j,i+b(j)) = .true.
                        update = .true.
                    end if
                end if
            end do
        end do
        ! print*, 'dp'
        ! do i=0, max_sat
        !     print*,i, dp(:,i), eated(:,i)
        ! end do
    end do

    ans = 0
    do i=0, max_sat
        ! print*, i, dp(:,i)
        if (dble(dp(1,i)) <= dble(t)-0.5d0) ans = max(ans, i)
    end do
    
    print*, ans
end program all_you_can_eat