给定一个包含 $N$ 个整数的数组 $A$，其中每个元素都在 $1$ 到 $M$ 之间。$N$ 为奇数。 同时给定一个长度为 $M$ 的数组 $cost$。 在一次操作中，你可以执行以下步骤： 选择一个下标 $i$ ($1 \le i \le N$) 和一个整数 $x$ ($1 \le x \le M$) 将 $A[i]$ 替换为 $\lfloor A[i]/x \rfloor$，代价为 $cost[x]$。

这里，$\lfloor \cdot \rfloor$ 表示向下取整函数，即 $\lfloor y \rfloor$ 是不超过 $y$ 的最大整数。 只要总代价不超过 $K$，你就可以执行操作。 在此条件下，求出能达到的 $median(A)$ 的最小值。 提醒一下，$median(A)$ 是数组 $A$ 排序后的中间元素。例如，$median([3, 1, 2]) = 2$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。接下来是各测试用例。 每个测试用例的第一行包含三个空格分隔的整数 $N, M, K$。 每个测试用例的第二行包含 $N$ 个空格分隔的整数 $A[1], A[2], \dots, A[N]$。 每个测试用例的第三行包含 $M$ 个空格分隔的整数 $cost[1], cost[2], \dots, cost[M]$。

数据范围

• $1 \le T \le 10^5$
• $1 \le N \le 10^6$
• $N$ 为奇数。
• $2 \le M \le 10^6$
• $0 \le K \le 10^9$
• $1 \le A[i] \le M$
• $1 \le cost[i] \le 10^9$
• 所有测试用例的 $N$ 之和不超过 $10^6$。
• 所有测试用例的 $M$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个整数，表示 $A$ 的最小可能中位数。

样例

输入 1

3
3 5 0
2 5 2
3 2 4 6 13
3 5 3
2 5 3
3 2 4 6 13
3 5 6
2 5 2
3 2 4 6 13

输出 1

2
2
1

说明

测试用例 1：无法进行任何操作，因此答案为 $median([2, 5, 2]) = 2$。

测试用例 2：执行以下操作： * 将 $A[3] = 3$ 除以 $x = 2$。这使得 $A[3] = 1$，代价为 $2$。 答案为 $median([2, 5, 1]) = 2$，这是最优的。

测试用例 3：执行以下操作： 将 $A[2] = 5$ 除以 $x = 3$。这使得 $A[2] = 1$，代价为 $4$。 将 $A[3] = 2$ 除以 $x = 2$。这使得 $A[3] = 1$，代价为 $2$。 答案为 $median([2, 1, 1]) = 1$，这是最优的。