K Best

bool test(int x);

double Left = 0;
double Right = 1000000;
double Result = 0;
while(fabs(Left - Right) > 1e-6)
{
	double Mid = (Left + Right) / 2;
	if(test(Mid))
	{
		Result = Mid;
		Left = Mid;
	}
	else
		Right = Mid;
}

bool test(double x)
{
	for(int i = 0; i < n; i ++)
		arr[i] = v[i] - x * w[i];
	sort(arr, arr + n);
	double sum = 0;
	for(int i = 0; i < k ;i ++)
	    sum += arr[n-1-i];
	if(sum >= 0)
		return true;
	else
		return false;
}

vector<int> construct(double x)
{
	vector<P> arr(n);
	for(int i = 0; i < n; i += 1)
		arr[i] = P(v[i] - x * w[i], i);
	sort(arr.begin(), arr.end());
	reverse(arr.begin(), arr.end());
	vector<int> result(k);
	for(int i = 0; i < k; i ++)
		result[i] = arr[i].second+1;
	return result;
}

#include <map>
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define P pair<double, int>
#define eps 1e-7
 
int n, v[200000], w[200000], k;
double arr[200000];
 
int check(double x)
{
	for(int i = 0; i < n; i ++)
		arr[i] = v[i] - x * w[i];
	sort(arr, arr + n);
	double sum = 0;
	for(int i = 0; i < k ;i ++)
	{
		sum += arr[n-1-i];
		if(sum < -eps)
			return false;
	}
	if(sum >= -eps)
		return true;
	else
		return false;
}
 
vector<int> construct(double x)
{
	vector<P> arr(n);
	for(int i = 0; i < n; i += 1)
		arr[i] = P(v[i] - x * w[i], i);
	sort(arr.begin(), arr.end());
	reverse(arr.begin(), arr.end());
	vector<int> result(k);
	for(int i = 0; i < k; i ++)
		result[i] = arr[i].second+1;
	return result;
}
 
int main()
{
	while(scanf("%d %d", &n, &k) == 2)
	{
		for(int i = 0; i < n; i ++)
			scanf("%d %d", v + i, w + i);
		double Left = 0, Right = 10000000;
		double result = 0;
		while(fabs(Left - Right) > 1e-6)
		{
			double Mid = (Left + Right) / 2;
			if(check(Mid))
			{
				result = Mid;
				Left = Mid;
			}
			else
				Right = Mid;
		}
		vector<int> vresult = construct(result);
		sort(vresult.begin(), vresult.end());
		for(int i = 0; i < vresult.size(); i ++)
		{
			if(i)
				cout << " ";
			cout << vresult[i];
		}
		cout << endl;
	}
	return 0;
}