← 返回题目列表

AtCoder · abc116_d

D. 各种寿司

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

分数: 400 点

问题陈述

有 N 寿司片。每件都有两个参数:“配料种类” t_i 和“美味” d_i。 你正在选择 K 其中 N 块吃。 您在这里的“满意度”将按如下方式计算:

  • 满意度是“基础总美味度”和“品种加成”的总和。
  • 基本总美味度是您所吃的食物的美味度之和。
  • 品种奖金是 x*x,其中 x 是您吃的食物中不同种类配料的数量。

您希望获得尽可能多的满足感。 找到最大的满足感。

约束

  • 1 \leq K \leq N \leq 10^5
  • 1 \leq t_i \leq N
  • 1 \leq d_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_N

输出

打印您可以获得的最大满意度。


示例输入 1

5 3
1 9
1 7
2 6
2 5
3 1

示例输出 1

26

如果你吃寿司 1,2 和 3:

  • 基本总美味是 9+7+6=22.
  • 品种奖金是 2*2=4.

因此,您的满意度将是 26,这是最佳的。


示例输入 2

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

示例输出 2

25

吃寿司是最佳选择 1,2,3 和 4.


示例输入 3

6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

示例输出 3

4900000016

请注意,输出可能不适合 32- 位整数类型。