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