eolymp
bolt
Try our new interface for solving problems

K Best

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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, ..., i_k} as

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

Giriş verilənləri

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 (1kn100000). The following n lines contain two integer numbers each - v_i and w_i (0v_i10^6,1w_i10^6, both the sum of all v_i and the sum of all w_i do not exceed 10^7).

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3 2
1 1
1 2
1 3
Çıxış verilənləri #1
1
2
Müəllif Dmitri Pavlov, Andrew Stankevich