K Ən Yaxşı
Demy'nin n qiymətli daşı var. Hər bir qiymətli daşın müəyyən bir dəyəri v_i və çəkisi w_i var.
Əri John son maliyyə böhranlarından sonra müflis olduğu üçün, Demy bəzi qiymətli daşlarını satmağa qərar verib. O, özü üçün k ən yaxşı qiymətli daşları saxlamağa qərar verib.
Demy, saxlayacağı qiymətli daşların xüsusi dəyərinin mümkün qədər böyük olmasını istəyir. Yəni, bəzi qiymətli daşlar dəstinin xüsusi dəyərini S = {i_1, i_2, ..., i_k} olaraq təyin edək.
Demy, bu k qiymətli daşları elə seçmək istəyir ki, onların xüsusi dəyəri mümkün qədər maksimal olsun. Ona bu işdə kömək edin.
Giriş verilənləri
Giriş faylının ilk sətri Demy'nin sahib olduğu qiymətli daşların sayı n və onun saxlamaq istədiyi qiymətli daşların sayı k ( 1 ≤ k ≤ n ≤ 100000 ) ilə başlayır. Sonrakı n sətir hər biri iki tam ədəd - v_i və w_i ( 0 ≤ v_i ≤ 10^6, 1 ≤ w_i ≤ 10^6, həm bütün v_i cəmi, həm də bütün w_i cəmi 10^7 -dən çox deyil) ehtiva edir.
Çıxış verilənləri
k ədəd çıxış edin - Demy'nin saxlamalı olduğu qiymətli daşların nömrələri. Bir neçə həll yolu varsa, hər hansı birini çıxış edin.