Problem Description

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.

Input Format

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 Format

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

3 4 5
1 3 4
2 3 5 6

6

Hint

【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