Computer Games
Description
Monocarp likes computer games. He uses the game distribution system "Mist" to download and install games.
There are $n$ games available in Monocarp's Mist account. The $i$-th game has two parameters:
- $s_i$ — the size of the game (the number of megabytes it occupies if installed);
- $r_i$ — the rating of the game for Monocarp.
Monocarp's computer has $m$ megabytes of free space. Monocarp won't install just one game; he wants to install at least $k$ games on his computer.
After installing the games, he will choose the $x$-th highest rated installed game and start playing it (i.e. if $x = 1$, he will choose the highest rated of the installed games, if $x = 2$, the second highest rated, and so on).
Your task is to calculate the maximum possible rating of a game that Monocarp can play, if he has to install at least $k$ games with total size not exceeding $m$. If it is impossible to install at least $k$ games, you should report it.
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains four integers $n$, $k$, $x$ and $m$ ($1 \le x \le k \le n \le 2 \cdot 10^5$; $1 \le m \le 2 \cdot 10^{14}$).
The second line contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le 10^9$).
The third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^9$).
Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
For each test case, print a single integer — the maximum possible rating of a game that Monocarp can play, if he has to install at least $k$ games with total size not exceeding $m$. If it is impossible to install at least $k$ games, you should print $-1$.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains four integers $n$, $k$, $x$ and $m$ ($1 \le x \le k \le n \le 2 \cdot 10^5$; $1 \le m \le 2 \cdot 10^{14}$).
The second line contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le 10^9$).
The third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^9$).
Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
Output
For each test case, print a single integer — the maximum possible rating of a game that Monocarp can play, if he has to install at least $k$ games with total size not exceeding $m$. If it is impossible to install at least $k$ games, you should print $-1$.
4
3 2 2 5
1 2 4
1 4 2
1 1 1 1
3
2
6 3 2 6
3 2 4 1 2 1
4 3 2 1 3 1
2 2 1 3
2 1
1 1
1
-1
3
1
Note
In the first example, Monocarp can install games $[1, 2]$ — the answer will be $1$, since it's the rating of the $2$-nd highest rated installed game. Games $[1, 3]$ will lead to the same answer. Games $[2, 3]$ can't be installed because their total size is $6$.
In the second example, the game size is greater than $m$, so the answer is $-1$.
In the third example, one of the possible set of games that lead to the answer $3$ is $[2, 4, 5, 6]$.