Various Sushi

题目描述

有 $N$ 片寿司。每片有两个参数：“配料种类” $t_i$ 和 “美味值” $d_i$ 。你要从这 $N$ 片中选择 $K$ 片来吃。你的“满意度”按如下方式计算：

满意度是“基础美味总和”和“多样性加成”的和。基础美味总和是你所吃的寿司的美味值之和。多样性加成是 $x*x$ ，其中 $x$ 是你所吃的寿司中不同配料种类的数量。

你希望使满意度尽可能大。求这个最大满意度。

输入按下列格式从标准输入给出： $N$ $K$ $t_1$ $d_1$ $t_2$ $d_2$ $.$ $.$ $.$ $t_N$ $d_N$

输出你能够获得的最大满意度。

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

4900000016

$1 \leq K \leq N \leq 10^5$ $1 \leq t_i \leq N$ $1 \leq d_i \leq 10^9$ 输入中的所有数值均为整数。如果你吃寿司 $1,2$ 和 $3$ ：

基础美味总和是 $9+7+6=22$ 。多样性加成是 $2*2=4$ 。

因此，你的满意度将是 $26$ ，这是最优的。
最优的是吃寿司 $1,2,3$ 和 $4$ 。
注意输出可能无法装入 32 位整数类型。

标签: AtCoder|abc116D

AtCoder|abc116D