Diamenty

Żona Bajtazara ma n diamentów, oznaczmy je numerami 1, 2, ..., n. Każdy z diamentów ma określoną wartość vi oraz wagę wi.

Po ostatniej kłotni z mężem żona Bajtazara postanowiła sprzedać niektóre ze swoich diamentów, postanowiła jednak, że zatrzyma dla siebie dokładnie k diamentów.

Zbiór diamentów S={i1, i2, ..., ik} ma dla żony Bajtazara wartość:
(vi1+vi2+...+vik)/ (wi1+wi2+...+wik)
Twoim zadaniem jest napisanie programu, który wyznaczy zbiór k diamentów, który dla żony Bajtazara ma największą wartość.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu wejścia zapisane są 2 liczby całkowite n, k (1 <= k <= n <= 100 000) oddzielone pojedynczym odstępem. W kolejnych n wierszach opisane są kolejne diamenty. W wierszu i+1-wszym znajdują się 2 liczby całkowite vi, wi (0 <= vi <=106, 1 <= wi <= 106) oddzielone pojedynczym odstępem. Zarówno suma wag wszystkich diamentów, jak i suma wartości wszystkich diamentów nie przekroczy 107.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać dokładnie k liczb całkowitych oddzielonych pojedynczymi odstępami, będących numerami diamentów które powinna zatrzymać żona Bajtazara. Numery te mogą być wypisane w dowolnej kolejności, jeśli istnieje wiele rozwiązań, Twój program może wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

3 2
1 1
1 2
1 3

prawidłową odpowiedzią jest:

1 2