← 返回题目列表

AtCoder · awc0041_d

D. 组建冒险家队伍

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

分数: 400 分

问题陈述

作为公会会长,高桥必须组建一支冒险者队伍来挑战地下城。

公会有 N 冒险家。每个冒险家 i (1 \leq i \leq N) 具有攻击力 A_i 和防御力 B_i.

高桥将准确选择 K 来自的冒险家 N 冒险者要组队。同一个冒险家不能被多次选择。队伍战斗力按照以下规则计算:

  • 让 S 是攻击力的总和 K 选定的冒险家。
  • 让 M 是最小防御力 K 选定的冒险家。
  • 该方战斗力为 S \times M.

无论队伍的总攻击力有多高,如果最低防御力较小,队伍的战斗力就会受到影响。

找出选择时该方可能的最大战斗力 K 冒险者被最佳选择。

约束

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^6
  • 1 \leq B_i \leq 10^6
  • 所有输入均为整数。

输入

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

第一行包含公会中冒险者的数量 N 以及为队伍选择的冒险家数量 K,用空格分隔。

的 i- 以下各项 N 行 (1 \leq i \leq N) 包含攻击力 A_i 和防御力 冒险家的 B_i 冒险家的 i,用空格分隔。

输出

在一行中以整数形式输出该方的最大可能战斗力。


示例输入 1

4 2
3 5
8 2
6 4
5 3

示例输出 1

36

示例输入 2

5 1
4 7
2 10
9 3
6 6
5 8

示例输出 2

40

示例输入 3

8 3
5 9
12 4
7 8
10 6
3 11
9 5
6 10
8 7

示例输出 3

150

示例输入 4

15 7
13 9
21 4
8 15
17 11
5 20
19 7
14 10
6 18
25 3
11 14
9 16
16 8
7 19
18 12
10 13

示例输出 4

880

示例输入 5

1 1
1000000 1000000

示例输出 5

1000000000000