103764: [Atcoder]ABC376 E - Max × Sum
Description
Score : $475$ points
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.
Output
问题陈述
给你长度为$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$，这是最小值。