Даша имеет n ювелирных украшений. Каждое украшение имеет стоимость wi и значимость для Даши vi. В связи с финансовым кризисом Даша решила продать некоторые украшения и сохранить только k из имеющихся. Чтобы решить, что именно сохранить, Даша вводит параметр важности для набора из выбранных k украшений, который вычисляет по следующей формуле:
\(\frac{\sum_{j=1}^k v_i}{\sum_{j=1}^k w_i}\)
Даша решает сохранить такие k украшений, для которых параметр важности будет максимально возможным. Помогите ей правильно выбрать украшения.
Входные данные
Первая строка ввода содержит числа n – количество ювелирных изделий у Даши и k – количество ювелирных изделий, которые планируется оставить (1 ≤ k ≤ n ≤ 100000).
В следующих n строках содержатся по два числа – vi и wi (0 ≤ vi ≤ 106,1≤wi≤106, обе суммы всех значений vi и wi не превосходят 107 каждая).
Выходные данные
Выведите k чисел – номера ювелирных украшений, которые следует оставить. Если существует несколько решений, то выведите любое из них.