A72009. 项目招标
编程题
入门
知识点
题目描述
某工程公司收到 N 份投标书，每份投标书来自一个供应商（用编号 t_i 表示），且该投标书的评审得分为 d_i（分值越高代表方案越优）。公司计划从中选取 K 份投标书进入最终候选名单。
最终候选名单的评审总得分由两部分构成：
- 基础分：所选 K 份投标书的评审得分之和。
- 多样性奖励：设 x 为所选投标书中不同供应商的个数，则奖励值为 x \times x。
公司的目标是最大化评审总得分（即基础分与多样性奖励之和）。请你计算这个最大可能值。
输入格式
第一行两个整数 N 和 K，分别表示投标书总数和需要选取的数量。
接下来 N 行，每行两个整数 t_i 和 d_i，分别表示第 i 份投标书的供应商编号和评审得分。
输出格式
输出一个整数，表示最大可能的评审总得分。
输入输出样例
输入 #1
5 3 1 9 1 7 2 6 2 5 3 1
输出 #1
26
输入 #2
7 4 1 1 2 1 3 1 4 6 4 5 4 5 4 5
输出 #2
25
输入 #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, K |
|---|---|
| 1 \sim 2 | 1 \le N \le 10, K=1 |
| 3 \sim 11 | 1 \le K \le N \le 100 |
| 12 \sim 20 | 1 \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。