K Найкращі
Демі має n коштовностей. Кожна з них характеризується певною цінністю v_i та вагою w_i.
Оскільки її чоловік Джон збанкрутував після недавніх фінансових криз, Демі вирішила продати частину своїх коштовностей. Вона планує залишити собі k найкращих.
Демі хоче зберегти такі коштовності, щоб їхня питома цінність була якомога вищою. Питома цінність набору коштовностей S = {i_1, i_2, ..., i_k} визначається як
Демі прагне вибрати k коштовностей так, щоб максимізувати їхню питому цінність. Допоможіть їй у цьому.
Вхідні дані
Перша строка вхідного файлу містить n - кількість коштовностей у Демі, та k - кількість коштовностей, які вона хоче залишити (1 ≤ k ≤ n ≤ 100000). Наступні n рядків містять по два цілі числа - v_i та w_i (0 ≤ v_i ≤ 10^6, 1 ≤ w_i ≤ 10^6, сума всіх v_i та сума всіх w_i не перевищують 10^7).
Вихідні дані
Виведіть k чисел - індекси коштовностей, які Демі повинна залишити. Якщо існує кілька можливих рішень, виведіть будь-яке з них.