Kth Value of Two Sorted Lists

a and b are each sorted in increasing order. Return the k-th smallest value of all their values combined (k = 1 is the smallest). Equal values count separately. The big tests only allow a few hundred reads.

Examples

Example 1

Input:

kth_of_two_sorted([2, 3, 6, 7, 9], [1, 4, 8, 10], 5)

Output:

6

Combined: 1, 2, 3, 4, 6, 7, 8, 9, 10. The 5th smallest is 6.

Example 2

Input:

kth_of_two_sorted([1, 2], [], 2)

Output:

2

Constraints

• 1 <= k <= len(a) + len(b) <= 4 * 10**5
• Both lists are sorted in non-decreasing order.
• -10**9 <= value <= 10**9
• The big tests count how many values you read from each list.