Chef's exam is near. There is a total of M subjects in his syllabus. Each subject consists of several topics. However, the questions will be set only from N topics. These topics are numbered 1 through N. The i^{th} topic belongs to C_{i}^{th} subject and takes T_{i} hours to cover.

Chef has only K hours left before the exam and wants to score the maximum marks. If Chef covers x_{1} number of topics of the 1^{st} subject, x_{2} number of topics of the 2^{nd} subject, and so on upto x_{M} number of topics of the M^{th} subject in the remaining K hours, he will get a total of $\lceil \frac{x_{1}}{2}$ \ $\rceil + \lceil \frac{x_{2}}{2}$ \ $\rceil + \cdots + \lceil \frac{x_{M}}{2}$ \ $\rceil$ marks in the exam. So Chef chooses the topics optimally.

Determine the maximum possible marks Chef can score in the exam.

Note: $\lceil x \rceil$ : Returns the smallest integer that is greater than or equal to x (i.e rounds up to the nearest integer). For example$, \lceil 1.5 \rceil = 2, \lceil 5 \rceil = 5$.

------ Input Format ------

• The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• Each test case contains three lines of input.
• The first line of each test case contains three space-separated integers N, M, K.
• The second line contains $N space-separated integers C_{1}, C_{2}, \dots, C_{N}$.
• The third line contains $N space-separated integers T_{1}, T_{2}, \dots, T_{N}$.

------ Output Format ------

For each test case, print a single line containing one integer - the maximum marks Chef can score.

------ Constraints ------

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ N$
$1 ≤ K ≤ 10^{9}$
$1 ≤ C_{i} ≤ M$
$1 ≤ T_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $5\cdot10^{5}$.

----- Sample Input 1 ------
3
3 2 2
1 1 2
1 1 2
4 3 2
1 1 2 2
1 1 2 1
5 3 10
1 1 1 2 3
1 5 2 5 1
----- Sample Output 1 ------
1
2
3

----- explanation 1 ------
Test case $1$: Chef covers the $1^{st}$ and $2^{nd}$ topic in $1 + 1 = 2$ hours. Both topics belongs to $1^{st}$ subject. He does not cover any topic of the second subject. By doing so, Chef gets $\lceil \frac{2}{2} \ \rceil + \lceil \frac{0}{2} \ \rceil$ = $\lceil \ 1 \ \rceil + \lceil \ 0 \ \rceil = 1$ marks.

Test case $2$: Chef covers the $1^{st}$ topic which belongs to the first subject and $4^{th}$ topic which belongs to the second subject in $1 + 1 = 2$ hours. There is no topic from the third subject. So Chef gets $\lceil \frac{1}{2} \ \rceil + \lceil \frac{1}{2} \ \rceil$ = $\lceil \ 0.5 \ \rceil + \lceil \ 0.5 \ \rceil = 1 + 1 = 2$ marks.

见题面

见题面