시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 50 30 27 60.000%

문제

어릴 때부터 게임에 미쳐 있는 준서는 석유급 학번을 가진 게임 덕후로 유명하다. 그의 취미는 재미있는 게임 을 찾아내는 것이다. 그런 준서는 딱 그에게 맞는 ‘스모그'라는 게임 플랫폼을 찾아냈다. ‘스모그'는 여러 게임 들을 온라인으로 대행 판매를 하여 구매한 유저에게 구매한 게임은 언제든지 다운로드를 할 수 있게 지원하는 플랫폼이다. ‘스모그'를 찾아낸 준서는 “어머, 이건 꼭 질러야해!”라고 소리를 질렀다. 그는 스스로를 ‘미락가(美楽家)'라고 생각하고 있기 때문에, 한 게임을 오래하기보다는 여러가지 게임을 즐기고 싶어한다. 하지만 모든 게임들을 다 해보기에는 현실의 돈 문제를 외면할 수 없었다. 그래서 준서는 게임들의 대략적인 평 들과 정보 를 보고 자신이 해당 게임을 할 때 어느 정도의 만족도를 가지는지를 예상했다. 준서는 최고의 가성비를 가지 는 게임 목록을 K개만 뽑아내려고 한다. 그러나 준서는 매우 큰 귀차니즘을 가지고 있어서 손으로 계산하는 것도, 직접 프로그램을 짜는 것도 귀찮아 한다. 따라서 그는 당신에게 프로그램 작성을 의뢰했다. 당신에게 구 매할 게임 수와 ‘스모그' 게임들의 정보가 주어졌을 때, 최대 가성비를 가지는 구매할 게임 목록을 출력하는 프로그램을 작성하라. 여기서 가성비란 원당 만족도(만족도/가격)를 의미한다.

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 ‘스모그’에 있는 게임의 수 N, 준서가 구매 할 게임의 수 K가 주어진다. (1 ≤ N ≤ 1000) (1 ≤ K ≤ N) 두번째 줄부터 N+1번째 줄까지 게임의 정보 i, c, h가 공백으로 구분되어 주어진다. i는 게임의 번호, c는 게임의 가격, h는 게임의 만족도를 의미한다. (1 ≤ i ≤ N) (1 ≤ c, h ≤ 108

출력

프로그램의 출력은 표준 출력으로 한다. 첫번째 줄부터 구매한 게임의 번호를 가성비를 기준으로 내림차순 출 력한다. 만약 가성비가 동일한 경우엔 가격을 기준으로 오름차순 출력한다. 만약 가격도 동일하다면, 번호를 오름차순 출력한다.

예제 입력

7 5
1 1000 1000
2 1000 1000
3 10000 1
4 10000 1
5 1000 5000
6 2000 10000
7 1000 10000

예제 출력

7
5
6
1
2

힌트