#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, f[N][N], ansf[N], tpf[N << 1], p[N];
ll g[N][N], ansg[N], tpg[N << 1];
struct node {
	int w, d;
}a[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) {
		return a.d < b.d;
	});
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j <= i; ++j) {
			f[i][j] = f[i + 1][j];
			g[i][j] = g[i + 1][j];
			if (a[i + 1].d > j) {
				if (f[i][j] < f[i + 1][j + 1] + 1 || (f[i][j] == f[i + 1][j + 1] + 1 && g[i][j] > g[i + 1][j + 1] + a[i + 1].w)) {
					f[i][j] = f[i + 1][j + 1] + 1;
					g[i][j] = g[i + 1][j + 1] + a[i + 1].w;
				}
			}
		}
	}
	int cnt = 1;
	for (int i = 1; i <= n; ++i) {
		int tot = 0;
		for (int j = 1; j <= cnt; ++j) {
			tpf[++tot] = ansf[j];
			tpg[tot] = ansg[j];
			if (a[i].d > ansf[j]) {
				tpf[++tot] = ansf[j] + 1;
				tpg[tot] = ansg[j] + a[i].w;
//				cerr << tpf[tot] << ' ' << tpg[tot] << '\n';
			}
		}
		cnt = min(tot, k);
		iota(p, p + 1 + tot, 0);
		sort(p + 1, p + 1 + tot, [&](int x, int y) {
			if (tpf[x] + f[i][tpf[x]] != tpf[y] + f[i][tpf[y]]) return tpf[x] + f[i][tpf[x]] > tpf[y] + f[i][tpf[y]];
			return tpg[x] + g[i][tpf[x]] < tpg[y] + g[i][tpf[y]];
		});
//		for (int j = 1; j <= tot; ++j) cerr << p[i] << ' ' << tpf[p[i]] << ' ' << tpg[p[i]] << '\n';
		for (int j = 1; j <= cnt; ++j) ansf[j] = tpf[p[j]], ansg[j] = tpg[p[j]];
	}
	for (int i = 1; i <= k; ++i) cout << ansf[i] << ' ' << ansg[i] << '\n';
	return 0;
}