alina20041002

23.06.2020 00:09 •  Информатика

даша имеет n ювелирных украшений. каждое украшение имеет стоимость wi и значимость для даши vi. в связи с финансовым кризисом даша решила продать некоторые украшения и сохранить только k из имеющихся. чтобы решить, что именно сохранить, даша вводит параметр важности для набора из выбранных k украшений, который вычисляет по следующей формуле:

ki=1vjki=1wj
даша решает сохранить такие k украшений, для которых параметр важности будет максимально возможным. ей правильно выбрать украшения.

входные данные
первая строка ввода содержит числа n – количество ювелирных изделий у даши и k – количество ювелирных изделий, которые планируется оставить (1kn100 000 ).

в следующих n строках содержатся по два числа – vi и wi (0vi106, 1wi106, обе суммы всех значений vi и wi не превосходят 107 каждая).

выходные данные
выведите k чисел – номера ювелирных украшений, которые следует оставить. если существует несколько решений, то выведите любое из них.