#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 2005;
int n, k;
struct Node {
	int w, d;
}a[N];
struct node {
	ll val;
	vector<int>v;
	inline bool operator < (node c) const {
		if (v.size() != c.v.size()) return v.size() < c.v.size();
		return val > c.val;
	}
}b;
void getv()
{
	priority_queue<pii>q;
	for (int i = 1; i <= n; ++i) {
		if (q.size() < a[i].d) {
			q.emplace(a[i].w, i);
		} else {
			if (q.top().first > a[i].w) {
				q.pop();
				q.emplace(a[i].w, i);
			}
		}
	}
	while (!q.empty()) {
		b.v.emplace_back(q.top().second);
		b.val += q.top().first;
		q.pop();
	}
}
void solve()
{
	priority_queue<node>q;
	set<vector<int>>se;
	q.emplace(b);
	se.emplace(b.v);
	while (!q.empty() && k--) {
		node c = q.top();
		q.pop();
		cout << c.v.size() << ' ' << c.val << '\n';
		for (int i = 0; i < c.v.size(); ++i) {
			if (c.v[i] < n && a[c.v[i]].d == a[c.v[i] + 1].d && (i + 1 == c.v.size() || c.v[i] + 1 < c.v[i + 1])) {
				c.val -= a[c.v[i]].w;
				++c.v[i];
				c.val += a[c.v[i]].w;
				if (se.emplace(c.v).second) {
					q.emplace(c);
				}
				c.val -= a[c.v[i]].w;
				--c.v[i];
				c.val += a[c.v[i]].w;
			}
		}
		for (int i = 0; i < c.v.size(); ++i) {
			int id = c.v[i], w = a[c.v[i]].w;
			c.val -= w;
			c.v.erase(c.v.begin() + i);
			if (se.emplace(c.v).second) {
				q.emplace(c);
			}
			c.v.emplace(c.v.begin() + i, id);
			c.val += w;
		}
	}
	while (k-- > 0) cout << "0 0\n";
}
bool en;
int main() {
	cerr << (&be - &en) / 1024.0 / 1024 << " MB\n--------------------------------" << endl;
#ifdef IAKIOI
	freopen("in.in", "r", stdin);
//	freopen("out.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i].w >> a[i].d;
	}
	sort(a + 1, a + 1 + n, [](Node a, Node b) {
		if (a.d != b.d) return a.d < b.d;
		return a.w < b.w;
	});
	getv();
	solve();
	return 0;
}