L. Computer Games
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

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$$$.

Example
Input
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
Output
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]$$$.