K. K-Best

У Демьяны есть $n$ драгоценностей. Каждая имеет ценность $v_i$ и вес $w_i$. Она решила оставить себе лишь $k$ лучших — лучших в смысле максимизации отношения суммы ценностей к сумме весов выбранных.

Помогите Демьяне выбрать $k$ драгоценностей требуемым образом.

На первой строке $n$ и $k$ ($1 \le k \le n \le 100\,000$). Следующие $n$ строк содержат пары целых чисел $v_i$, $w_i$ ($0 \le v_i \le 10^6$, $1 \le w_i \le 10^6$, сумма всех $v_i$ не превосходит $10^7$, сумма всех $w_i$ также не превосходит $10^7$).

Выведите $k$ различных чисел от 1 до $n$ — номера драгоценностей. Если оптимальных ответов несколько, выведите любой.