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:
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$$$.
43 2 2 51 2 41 4 21 1 1 1326 3 2 63 2 4 1 2 14 3 2 1 3 12 2 1 32 11 1
1 -1 3 1
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]$$$.
Name |
---|