#P2170. 选学霸

    ID: 1188 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp并查集概率论统计背包洛谷原创

选学霸

题目描述

老师想从 nn 名学生中选 mm 人当学霸,但有 kk 对人实力相当,如果实力相当的人中,一部分被选上,另一部分没有,同学们就会抗议。所以老师想请你帮他求出他该选多少学霸,才能既不让同学们抗议,又与原来的 mm 尽可能接近。

输入格式

第一行,三个正整数 n,m,kn,m,k

接下来 kk 行,每行 22 个数,表示一对实力相当的人的编号(编号为 1,2,n1,2,\cdots n)。

输出格式

共一行,表示既不让同学们抗议,又与原来的 mm 尽可能接近的选出学霸的数目。

如果有两种方案与 mm 的差的绝对值相等,选较小的一种。

4 3 2
1 2
3 4
2

提示

对于 100%100\% 的数据,满足 1n,m2×1041 \le n,m \le 2 \times 10^4