← 返回题目列表

AtCoder · abc376_e

H. 最大值 × 总和

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

给定长度序列 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 测试用例;解决它们中的每一个。

约束

  • 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,这是最小值。