Задача №957. Даша и кризис
Даша имеет \(n\) ювелирных украшений. Каждое украшение имеет стоимость \(w_i\) и значимость для Даши \(v_i\). В связи с финансовым кризисом Даша решила продать некоторые украшения и сохранить только \(k\) из имеющихся. Чтобы решить, что именно сохранить, Даша вводит параметр важности для набора из выбранных \(k\) украшений, который вычисляет по следующей формуле:
\(\frac{\sum_{j=1}^k v_i}{\sum_{j=1}^k w_i}\)Даша решает сохранить такие \(k\) украшений, для которых параметр важности будет максимально возможным. Помогите ей правильно выбрать украшения.
Первая строка ввода содержит числа \(n\) – количество ювелирных изделий у Даши и \(k\) – количество ювелирных изделий, которые планируется оставить \( (1 \leq k \leq n \leq 100\,000) \).
В следующих \(n\) строках содержатся по два числа – \(v_i\) и \(w_i (0 \leq v_i \leq 10^6, 1 \leq w_i \leq 10^6\), обе суммы всех значений \(v_i\) и \(w_i\) не превосходят \(10^7\) каждая).
Выведите \(k\) чисел – номера ювелирных украшений, которые следует оставить. Если существует несколько решений, то выведите любое из них.
3 2 1 1 1 2 1 3
1 2