#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, ct, up[N], t[N];
struct Node {
	int w, d;
}a[N];
vector<int>v[N];
set<vector<int>>se;
struct node {
	ll val;
	vector<int>ve;
	node()
	{
		val = 0;
	}
	inline void push(int x)
	{
		ve.emplace_back(x);
		val += a[x].w;
	}
	inline bool operator < (node a) const {
		return val > a.val;
	}
};
priority_queue<node>q;
void dfs(int u, int left, node c)
{
	if (n - u + 1 < left) return;
	if (u > n) {
		if (se.emplace(c.ve).second) {
			q.emplace(c);
//			cerr << c.val << '\n';
//			for (int x : c.ve) cerr << x << ' ';
//			cerr << '\n';
		}
		return;
	}
	dfs(u + 1, left, c);
	if (left && up[a[u].d]) {
		c.push(u);
		--up[a[u].d];
		dfs(u + 1, left - 1, c);
		++up[a[u].d];
	}
}
void init(int lim)
{
	while (!q.empty()) q.pop();
	dfs(1, lim, node());
}
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;
	});
	for (int i = 1; i <= n; ++i) {
		++t[a[i].d];
	}
	int tot = 0;
	for (int i = 1; i <= n; ++i) {
		++ct;
		while (ct && up[i] < t[i]) {
			--ct;
			++up[i];
			++tot;
		}
	}
	for (int i = tot; i >= 0; --i) {
//		cerr << "Round " << i << '\n';
		init(i);
		while (!q.empty()) {
			node c = q.top();
			q.pop();
			cout << i << ' ' << c.val << '\n';
			if (!--k) return 0;
			for (int i = 0; i < c.ve.size(); ++i) {
				if (((c.ve[i] + 1 == c.ve.size() && c.ve[i] < n) || (c.ve[i] + 1 < c.ve[i + 1])) && a[c.ve[i]].d == a[c.ve[i] + 1].d) {
					c.val -= a[c.ve[i]].w;
					++c.ve[i];
					c.val += a[c.ve[i]].w;
					if (se.emplace(c.ve).second) {
						q.emplace(c);
					}
					c.val -= a[c.ve[i]].w;
					--c.ve[i];
					c.val += a[c.ve[i]].w;
				}
			}
		}
	}
	return 0;
}