A72009 | $项目招标$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

某工程公司收到 N 份投标书，每份投标书来自一个供应商（用编号 t_i 表示），且该投标书的评审得分为 d_i（分值越高代表方案越优）。公司计划从中选取 K 份投标书进入最终候选名单。 最终候选名单的评审总得分由两部分构成： 基础分：所选 K 份投标书的评审得分之和。 多样性奖励：设 x 为所选投标书中不同供应商的个数，则奖励值为 x \times x。 公司的目标是最大化评审总得分（即基础分与多样性奖励之和）。请你计算这个最大可能值。

第一行两个整数 N 和 K ，分别表示投标书总数和需要选取的数量。 接下来 N 行，每行两个整数 t_i 和 d_i ，分别表示第 i 份投标书的供应商编号和评审得分。

输出一个整数，表示最大可能的评审总得分。

输入 #1

输出 #1

输入 #2

输出 #2

输入 #3

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

输出 #3

4900000016

样例说明 样例 #1 选取第 1,2,3 份投标书（供应商编号分别为 1,1,2）： 基础分 = 9 + 7 + 6 = 22 不同供应商个数 x = 2（供应商 1 和 2），多样性奖励 = 2 \times 2 = 4 总得分 = 22 + 4 = 26 可以证明这是最优方案。 样例 #2 选取第 1,2,3,4 份投标书（供应商编号分别为 1,2,3,4）： 基础分 = 1 + 1 + 1 + 6 = 9 不同供应商个数 x = 4，多样性奖励 = 4 \times 4 = 16 总得分 = 9 + 16 = 25 可以证明这是最优方案。 样例 #3 注意计算结果可能超出 32 位有符号整数范围，需要使用 64 位整数类型（如 long long）。 数据范围 测试点编号N, K1 \sim 21 \le N \le 10, K=13 \sim 111 \le K \le N \le 10012 \sim 201 \le K \le N \le 10^5对于 100\% 的数据，满足 1 \leq K \leq N \leq 10^5，1 \leq t_i \leq N，1 \leq d_i \leq 10^9。

C++ 编辑器

输入

输出