D - Forming an Adventurer Party Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はギルドマスターとして、ダンジョン攻略に挑む冒険者パーティを編成することになりました。

ギルドには N 人の冒険者が所属しています。各冒険者 i（1 \leq i \leq N）には、攻撃力 A_i と防御力 B_i が設定されています。

高橋君は N 人の冒険者の中からちょうど K 人を選んでパーティを編成します。ただし、同じ冒険者を2回以上選ぶことはできません。パーティの戦闘力は以下のルールで計算されます：

  • 選んだ K 人の冒険者の攻撃力の合計を S とする
  • 選んだ K 人の冒険者の防御力の最小値を M とする
  • パーティの戦闘力は 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

1 行目には、ギルドに所属する冒険者の人数 N と、パーティに選ぶ人数 K が、スペース区切りで与えられます。

続く N 行のうち i 番目の行（1 \leq i \leq N）には、冒険者 i の攻撃力 A_i と防御力 B_i が、スペース区切りで与えられます。

出力

パーティの戦闘力としてありうる最大値を整数として 1 行で出力してください。

入力例 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

Score : 400 pts

Problem Statement

As a guild master, Takahashi must form a party of adventurers to challenge a dungeon.

The guild has N adventurers. Each adventurer i (1 \leq i \leq N) has an attack power A_i and a defense power B_i.

Takahashi will select exactly K adventurers from the N adventurers to form a party. The same adventurer cannot be selected more than once. The party's combat power is calculated according to the following rules:

  • Let S be the sum of the attack powers of the K selected adventurers.
  • Let M be the minimum defense power among the K selected adventurers.
  • The party's combat power is S \times M.

No matter how high the total attack power of the party is, if the minimum defense power is small, the party's combat power will suffer.

Find the maximum possible combat power of the party when the selection of K adventurers is chosen optimally.

Constraints

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^6
  • 1 \leq B_i \leq 10^6
  • All inputs are integers.

Input

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

The first line contains the number of adventurers in the guild N and the number of adventurers to select for the party K, separated by a space.

The i-th of the following N lines (1 \leq i \leq N) contains the attack power A_i and defense power B_i of adventurer i, separated by a space.

Output

Output the maximum possible combat power of the party as an integer on a single line.

Sample Input 1

4 2
3 5
8 2
6 4
5 3

Sample Output 1

36

Sample Input 2

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

Sample Output 2

40

Sample Input 3

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

Sample Output 3

150

Sample Input 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

Sample Output 4

880

Sample Input 5

1 1
1000000 1000000

Sample Output 5

1000000000000