Demy has n jewels. Each of her jewels has some value v_i and weight w_i.

Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep k best jewels for herself. She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels S = {i₁, i₂, …,i_k} as

.

Demy would like to select such k jewels that their specific value is maximal possible. Help her to do so.

The first line of the input file contains n — the number of jewels Demy got, and k — the number of jewels she would like to keep (1 ≤ k ≤ n ≤ 100 000).

The following n lines contain two integer numbers each — v_i and w_i (0 ≤ v_i ≤ 10⁶, 1 ≤ w_i ≤ 10⁶, both the sum of all v_i and the sum of all w_i do not exceed 10⁷).

Output k numbers — the numbers of jewels Demy must keep. If there are several solutions, output any one.

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <sstream>

#include <numeric>

#include <cstring>

#include <bitset>

#include <string>

#include <deque>

#include <stack>

#include <cmath>

#include <queue>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 100010;

const double eps = 1e-9;

struct info

{

    double w, v, d;

    int id;

    bool operator<(const info &rhs)const

    {

        return d > rhs.d;

    }

};

info A[N];

double getnewk(int n, int k, double r)

{

    double V = 0.0, W = 0.0;

    for (int i = 0; i < n; ++i)

        A[i].d = A[i].v - r * A[i].w;

    sort(A, A + n);

    for (int i = 0; i < k; ++i)

    {

        V += A[i].v;

        W += A[i].w;

    }

    return V / W;

}

int main(void)

{

    int n, k, i;

    while (~scanf("%d%d", &n, &k))

    {

        for (i = 0; i < n; ++i)

        {

            scanf("%lf%lf", &A[i].v, &A[i].w);

            A[i].id = i + 1;

        }

        double ans = 1, temp = 1;

        while (1)

        {

            temp = getnewk(n, k, ans);

            if (fabs(temp - ans) < eps)

                break;

            ans = temp;

        }

        for (i = 0; i < k; ++i)

            printf("%d%s", A[i].id, i == k - 1 ? "\n" : " ");

    }

    return 0;

}