Students' Revenge

题意翻译

有一个主席每天要处理繁重的事务，但学生们仍然对他非常反感。现在有$n$个任务，学生们会选出$p$个，在这其中主席会选出$k$个来完成，剩下的$n-k$个不会完成。 完成一项任务会使主席的头发变白$a_i$，不完成就会使学生们的不满意度增加$b_i$。主席会使学生们的不满意度尽可能少，在此基础上使自己的头发变白尽可能少。 但是学生们想要使主席的头发变白尽可能多，其次使得学生们的不满意度尽可能大。 求此时主席有多少白头发，并有多少的不满意度。 **输入格式：** 输入共$n+1$行，第$1$行分别为为$n,p,k$，代表有$n$个任务，学生们选出$p$个，主席从这$p$个中选出$k$个来完成。 接下来的$n$行，每行两个整数，第$i$行的$a_i,b_i$分别表示完成第$i$项任务会使主席的头发变白多少，不完成第$i$项任务会使学生们的满意度增加多少。 $1\le k\le p\le n\le 10^5,1\le a_i,b_i\le 10^9$ **输出格式：** 按顺序输出$p$个整数，表示主席**依次**按他的偏好选了哪$p$个任务解决。

题目描述

A student's life is fraught with complications. Some Berland University students know this only too well. Having studied for two years, they contracted strong antipathy towards the chairperson of some department. Indeed, the person in question wasn't the kindest of ladies to begin with: prone to reforming groups, banning automatic passes and other mean deeds. At last the students decided that she just can't get away with all this anymore... The students pulled some strings on the higher levels and learned that the next University directors' meeting is going to discuss $ n $ orders about the chairperson and accept exactly $ p $ of them. There are two values assigned to each order: $ a_{i} $ is the number of the chairperson's hairs that turn grey if she obeys the order and $ b_{i} $ — the displeasement of the directors if the order isn't obeyed. The students may make the directors pass any $ p $ orders chosen by them. The students know that the chairperson will obey exactly $ k $ out of these $ p $ orders. She will pick the orders to obey in the way that minimizes first, the directors' displeasement and second, the number of hairs on her head that turn grey. The students want to choose $ p $ orders in the way that maximizes the number of hairs on the chairperson's head that turn grey. If there are multiple ways to accept the orders, then the students are keen on maximizing the directors' displeasement with the chairperson's actions. Help them.

输入输出格式

输入格式

The first line contains three integers $ n $ ( $ 1<=n<=10^{5} $ ), $ p $ ( $ 1<=p<=n $ ), $ k $ ( $ 1<=k<=p $ ) — the number of orders the directors are going to discuss, the number of orders to pass and the number of orders to be obeyed by the chairperson, correspondingly. Each of the following $ n $ lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=10^{9} $ ), describing the corresponding order.

输出格式

Print in an arbitrary order $ p $ distinct integers — the numbers of the orders to accept so that the students could carry out the revenge. The orders are indexed from 1 to $ n $ in the order they occur in the input. If there are multiple solutions, you can print any of them.

输入输出样例

输入样例 #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 

说明

In the first sample one of optimal solutions is to pass orders 1, 2, 3. In this case the chairperson obeys orders number 1 and 2. She gets 10 new grey hairs in the head and the directors' displeasement will equal 3. Note that the same result can be achieved with order 4 instead of order 3. In the second sample, the chairperson can obey all the orders, so the best strategy for the students is to pick the orders with the maximum sum of $ a_{i} $ values. The chairperson gets 58 new gray hairs and the directors' displeasement will equal 0.