P10417 [Lanqiao Cup 2023 National A] The $K$-th Smallest Sum

Given two sequences $A$ and $B$, with lengths $n$ and $m$, respectively. Define another sequence $C$ that contains all pairwise sums of numbers from $A$ and $B$ ($C$ has a total of $n\times m$ numbers). Ask what the $K$-th smallest number in $C$ is. Note that duplicate values must be counted multiple times. For example, in $1,1,2,3$, both the smallest and the second smallest are $1$, and $3$ is the $4$-th smallest.

The first line contains three integers $n,m,K$, separated by one space between adjacent integers. The second line contains $n$ integers, representing $A_1,A_2,\ldots,A_n$, separated by one space between adjacent integers. The third line contains $m$ integers, representing $B_1,B_2,\ldots,B_m$, separated by one space between adjacent integers.

Output one line containing one integer, which is the answer.

**【Constraints and Conventions for Testcases】** - For $40\%$ of the testcases, $n,m\le 5000$, $A_i,B_i\le 1000$. - For all testcases, $1\le n,m\le 10^5$, $1\le A_i,B_i\le 10^9$, $1\le K\le n\times m$. Translated by ChatGPT 5