m, n = gets.split.map(&:to_i)
books = (1..m).map { gets.split.map(&:to_i) }
shelfs = (1..n).map { gets.split.map(&:to_i) }
tsp = Array.new(2 ** n, 0)
tsp[0] = 0
(1..2**n).each do |x|
    (0..n-1).each do |i|
        next if x[i] == 0
        c, b = shelfs[i]
        y = x - (1 << i)
        k = tsp[y]
        while k < m && books[k][0] <= c && books[k][1] <= b
            c -= books[k][0]
            b -= books[k][1]
            k += 1
        end
        tsp[x] = k if k > tsp[x]
    end
end
p tsp[-1]
