题目描述

给定两个长度均为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$ 和 $B = (B_1, B_2, \dots, B_N)$。

现在请你从编号 $1 \sim N$ 中选出恰好 $K$ 个不同的下标，组成一个集合 $S$。

我们定义目标值为：集合 $S$ 中元素对应 $A_i$ 的最大值 乘以 集合 $S$ 中元素对应 $B_i$ 的总和，也就是：

$$\left(\max_{i \in S} A_i\right) \times \left(\sum_{i \in S} B_i\right) $$

其中 $i\in S$ 表示 $i$ 属于集合 $S$ 中的值

请求出这个目标值的最小可能取值。本题有多组测试数据。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

接下来依次输入 $T$ 组测试数据。每组数据格式为：

• 第一行两个正整数 $N, K$
• 第二行 $N$ 个正整数，表示序列 $A$
• 第三行 $N$ 个正整数，表示序列 $B$

输出格式

对于每组测试数据，输出一行一个整数，表示该组数据的答案。

3
3 2
3 7 6
9 2 4
5 3
6 4 1 5 9
8 6 5 1 7
10 6
61 95 61 57 69 49 46 47 14 43
39 79 48 92 90 76 30 16 30 94

42
60
14579

样例 1 解释说明

第一组数据中，选择下标 $S = \{2, 3\}$，此时 $\max(A) = \max(7, 6) = 7$，$\operatorname{sum}(B) = 2+4=6$，乘积为 $7 \times 6 = 42$，这是所有选法里的最小值。

数据规模与约定

对于全部的测试点，保证：

• $1 \le T \le 2 \times 10^5$
• $1 \le K \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le 10^6$
• 所有测试点的 $N$ 总和不超过 $2 \times 10^5$
• 所有输入数值均为整数