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 чисел - номера драгоценностей, которые Деми должна оставить. Если существует несколько решений, вы можете вывести любое из них.