Score : $475$ points

问题陈述

给定两个长度为 $N$ 的序列：$A = (A_1, A_2, \dots, A_N)$ 和 $B = (B_1, B_2, \dots, B_N)$。
设 $S$ 是 $\lbrace1, 2, \dots, N\rbrace$ 的一个大小为 $K$ 的子集。在这里，找到以下表达式的最小可能值：

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

你给出了 $T$ 个测试用例；解决每一个。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given sequences of length $N$: $A = (A_1, A_2, \dots, A_N)$ and $B = (B_1, B_2, \dots, B_N)$.
Let $S$ be a subset of $\lbrace1, 2, \dots, N\rbrace$ of size $K$. Here, find the minimum possible value of the following expression:

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

You are given $T$ test cases; solve each of them.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^6$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ denotes the $i$-th test case.

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

Each test case is given in the following format:

$N$ $K$

$A_1$ $A_2$ $\dots$ $A_N$

$B_1$ $B_2$ $\dots$ $B_N$

Output

Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

Sample Input 1

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

Sample Output 1

42
60
14579

In the first test case, for $S = \{2, 3\}$, the value of the expression is $7 \times (2 + 4) = 42$, which is the minimum.