3639번 - K Best 스페셜 저지다국어

문제

Demy has $n$ jewels. Each of her jewels has some value $v_i$ and weight $w_i$.

Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep $k$ best jewels for herself.

She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels $S = \{i_1, i_2, \ldots, i_k\}$ as

$$s(S) = \frac{\sum\limits_{j = 1}^k{v_{i_j}}}{\sum\limits_{j = 1}^k{w_{i_j}}}.$$

Demy would like to select such $k$ jewels that their specific value is maximal possible. Help her to do so.

입력

The first line of the input file contains $n$ --- the number of jewels Demy got, and $k$ --- the number of jewels she would like to keep (1ドル \le k \le n \le 100,000円$).

The following $n$ lines contain two integer numbers each --- $v_i$ and $w_i$ (0ドル \le v_i \le 10^6,ドル 1ドル \le w_i \le 10^6,ドル both the sum of all $v_i$ and the sum of all $w_i$ do not exceed 10ドル^7$).

출력

Output $k$ numbers --- the numbers of jewels Demy must keep. If there are several solutions, output any one.

제한

힌트