103764: [Atcoder]ABC376 E - Max × Sum

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:

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.

问题陈述

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

你有$T$个测试用例；解决每一个。

约束条件

• $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$
• 所有测试用例中$N$的总和最多为$2 \times 10^5$。
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出。这里，$\mathrm{case}_i$表示第$i$个测试用例。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例的格式如下：

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$

输出

打印$T$行。第$i$行应包含第$i$个测试用例的答案。

示例输入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

示例输出1

42
60
14579

在第一个测试用例中，对于$S = \{2, 3\}$，表达式的值为$7 \times (2 + 4) = 42$，这是最小值。