Merge Two Sorted Arrays and Find the K-th Smallest Element

You are given two sorted arrays A and B containing N and M integers respectively. Your task is to merge these two arrays into one sorted array and find the \(K\)-th smallest element in the merged array. Note that \(K\) is 1-indexed.

If the merged array contains less than \(K\) elements, output -1.

Formally, if the merged array is \(C = A \cup B\) sorted in non-decreasing order, you need to find \(C[K-1]\), if it exists. Otherwise, output \(-1\).

inputFormat

The first line contains three space-separated integers: N, M and K, where:

• N is the number of elements in the first sorted array A.
• M is the number of elements in the second sorted array B.
• K is the 1-indexed position of the element to find in the merged array.

The second line contains N integers representing the sorted array A (if N is 0, this line will be empty).

The third line contains M integers representing the sorted array B (if M is 0, this line will be empty).

outputFormat

Output a single integer: the \(K\)-th smallest element after merging the two arrays. If the merged array has fewer than \(K\) elements, output -1.

3 4 5
2 5 8
1 3 6 9

6