分数: 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