分数: 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- 位整数类型。