Q:

kth smallest number

Suppose we have n (1<=n<=10^3) sorted arrays of sizes A1, A2, .... An. (1<=Ai<=10^3). We need to kind the kth smallest integer from the unique combination these arrays. Is there an efficient method to do this with complexity less than O(A1 + A2.. + An)?
Can be be solved something similar to binary search?
PS: I have a similar problem here, but could not understand how to extend it for unique elements.
EDIT 1: I think some of you misunderstood the question. Let us take an example:
N = 3, 
A1 = 1, 1, 2, 3
A2 = 6, 7, 9
A3 = 1, 6, 8
The unique combination of above arrays is {1, 2, 3, 6, 7, 8, 9}. Now suppose I want the 2nd element it should return 2 and for 4th element it should return 6.

A:

It is possible in O(k n log n):

Make a min-heap with the minimal element from each array.
Repeat k times:

Look at the minimum element q in the min-heap and remember it
Extract from min-heap while minimum equals to q.
For each extracted element, put the first element larger than q from the corresponding array

Answer is the minimum element in min-heap

Python code:
import heapq
import bisect

def kth(A, k):
    h = []

    for idx,a in enumerate(A):
        if len(a) > 0:
            heapq.heappush(h, (a[0], idx))

    for i in xrange(k):
        if len(h) == 0:
            return None

        val, _ = h[0]

        while (len(h) > 0) and (h[0][0] == val):
            _, idx = heapq.heappop(h)
            nxt = bisect.bisect_right(A[idx], val)
            if nxt < len(A[idx]):
                heapq.heappush(h, (A[idx][nxt], idx))

    if len(h) > 0:
        return h[0][0]
    return None

