배달 후보 카드 고르기

문제

한 배달 앱은 고객이 여러 가게의 배달 조건을 비교할 수 있도록 후보 카드를 보여 준다. 각 카드에는 배달비와 예상 배달 시간이 적혀 있다. 이번 화면에는 후보가 N개 있지만, 화면 공간이 제한되어 있어 그중 K개만 표시해야 한다. 앱은 모든 후보에 같은 기준을 적용하여 표시할 카드와 그 순서를 결정한다. 후보 번호는 입력으로 주어진 순서에 따라 1번부터 N번까지 붙인다. 첫 번째로 입력된 후보가 1번이고, 마지막으로 입력된 후보가 N번이다. 이 번호는 후보를 구분하기 위한 고유한 값이며, 정렬한 뒤에도 바뀌지 않는다. 서로 다른 후보의 배달비와 예상 배달 시간이 모두 같을 수 있다. 앱은 배달비가 적은 후보를 먼저 놓는다. 배달비가 같다면 예상 배달 시간이 짧은 후보를 먼저 놓는다. 배달비와 예상 배달 시간이 모두 같다면 후보 번호가 작은 후보를 먼저 놓는다. 예상 배달 시간은 배달비가 같은 후보 사이에서만 비교한다. 따라서 배달비가 더 적은 후보는 예상 배달 시간이 더 길어도 배달비가 더 많은 후보보다 앞에 놓인다. 모든 후보를 이 기준으로 정렬한 뒤 맨 앞의 K개를 화면에 표시한다. K는 1 이상 N 이하이므로 표시할 후보가 부족한 경우는 없다. K번째 위치와 그다음 위치의 후보가 같은 배달비와 예상 배달 시간을 가지더라도 번호가 작은 후보부터 선택하여 정확히 K개만 표시한다. 화면에 표시될 후보 번호를 실제 표시 순서대로 구하는 프로그램을 작성한다. 선택한 번호를 다시 번호순으로 정렬해서는 안 된다.

입력

첫째 줄에 후보 수 N과 표시할 카드 수 K가 공백으로 구분되어 주어진다.
다음 N개 줄 중 i번째 줄에 i번 후보의 배달비 F_i와 예상 배달 시간 T_i가 공백으로 구분되어 주어진다.
모든 입력값은 정수이며 1 ≤ K ≤ N ≤ 1,000, 0 ≤ F_i ≤ 10,000, 1 ≤ T_i ≤ 180이다.

출력

화면에 표시될 K개 후보의 번호를 표시 순서대로 공백 하나로 구분하여 한 줄에 출력한다. 번호는 1부터 시작하며, 배달비와 시간이 모두 같은 경우에는 번호가 작은 후보를 먼저 출력한다.

5 3
2000 25
1000 40
1000 25
0 70
1000 25

4 3 5

4 4
700 30
700 30
700 30
700 30

1 2 3 4

3 1
500 10
0 180
500 1

2

출처: Devin.KR 자체 제작