Given two arrays A and B, how do I answer queries asking the qth minimum sum of A[i]+B[j]?


I am given two arrays A and B of same size K (K<=20000). There can be upto 500 queries (offline), each asking the qth minimum sum a+b such that a belongs to A and b belongs to B (q<=10000). How do I answer these queries efficiently?
One way would be to iterate over all pairs but that is too slow for me.