学生的生活充满了复杂性。伯兰大学的一些学生对此深有体会。学习了两年,他们对某系主任产生了强烈的反感。事实上,这个人一开始就不是最善良的女士:倾向于改革团体、禁止自动通行证和其他卑鄙行为。最后,学生们决定她不能再逃避这一切了……
学生们对上级进行了一些操纵,得知下次大学董事会议将讨论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。