class Array
    def accum
        ac = Array.new(size + 1)
        ac[0] = 0
        (1..size).each do |i|
            ac[i] = ac[i-1] + self[i-1]
        end
        ac
    end

    def bsearch_last_index(l = 0, r = size - 1, &pred)
        return nil if l > r
        c = (l + r) / 2 
        if pred[self[c]]
            bsearch_last_index(c+1, r, &pred) || c
        else
            bsearch_last_index(l, c-1, &pred)
        end
    end
end

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) }
accum = books.transpose.map(&:accum).transpose

cache = {}
tsp = Array.new(2 ** n, 0)
tsp[0] = 0
(1..2**n-1).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]
        l = accum.bsearch_last_index(0, m){|aw, at| aw - accum[k][0] <= c && at - accum[k][1] <= b}
        tsp[x] = l if l > tsp[x]
    end
end
p tsp[-1]
