← 返回题目列表

Codeforces · 332/C

C. 学生的复仇

中文机器翻译题面 查看原题

学生的生活充满了复杂性。伯兰大学的一些学生对此深有体会。学习了两年,他们对某系主任产生了强烈的反感。事实上,这个人一开始就不是最善良的女士:倾向于改革团体、禁止自动通行证和其他卑鄙行为。最后,学生们决定她不能再逃避这一切了……

学生们对上级进行了一些操纵,得知下次大学董事会议将讨论n条有关主席的命令,并准确接受其中p条。每个命令都有两个值:ai 是主席在遵守命令时头发变白的数量;bi 是董事不遵守命令时的不满程度。学生可以让董事通过他们选择的任何命令。学生们知道主席将严格遵守这 p 个命令中的 k 个命令。她会选择要服从的命令,首先要尽量减少董事的不满,其次要尽量减少她头上白发的数量。

学生们希望以最大化主席头上变白的头发数量的方式来选择 p 阶。如果有多种方式接受命令,那么学生们就会热衷于最大化董事们对主席行为的不满。帮助他们。

输入

第一行包含三个整数n(1≤n≤105)、p(1≤p≤n)、k(1≤k≤p)——分别是董事要讨论的命令数、要通过的命令数和主席要遵守的命令数。接下来的n行每行包含两个整数ai和bi(1≤ai,bi≤109),描述相应的顺序。

输出

以任意顺序打印p个不同的整数——学生们要接受的命令数量,以便他们可以进行复仇。这些顺序按照它们在输入中出现的顺序从 1 到 n 进行索引。如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

5 3 2
5 6
5 8
1 3
4 3
4 11

输出 #1

3 1 2

输入 #2

5 3 3
10 18
18 17
10 20
20 18
20 18

输出 #2

2 4 5

注意

在第一个示例中,最佳解决方案之一是通过命令 1、2、3。在这种情况下,主席遵守命令 1 和 2。她的头上长出了 10 根新的白发,董事们的不满度将等于 3。请注意,使用命令 4 而不是命令 3 可以实现相同的结果。

在第二个样本中,主席可以服从所有命令,因此学生的最佳策略是选择 ai 值之和最大的命令。董事长新增58根白发,董事们的不满度等于0。