#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, k, a, b;
cin >> n >> k;
vector<vector<int>> vals(n + 1, vector<int>());
vector<pair<int, int>> valss;
for (int i = 0; i < n; i++) {
cin >> a >> b;
vals[b].push_back(a);
valss.push_back({b, a});
}
sort(valss.begin(), valss.end());
for (int i = 1; i <= n; i++)
sort(vals[i].begin(), vals[i].end());
vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>(n + 1, {LLONG_MAX, LLONG_MAX}));
if (k <= 2) {
for (int i = 0; i < n; i++) {
if (i == 0) {
dp[0][0] = {0, LLONG_MAX};
if (vals[1].size() == 1)
dp[0][1] = {vals[1][0], LLONG_MAX};
else if (vals[1].size() >= 2)
dp[0][1] = {vals[1][0], vals[1][1]};
continue;
}
int crntsum = 0;
dp[i][0] = {0, LLONG_MAX};
for (int j = 0; j < (int)vals[i + 1].size(); j++) {
crntsum += vals[i + 1][j];
for (int k = j + 1; k <= i + 1; k++) {
if (dp[i - 1][k - j - 1].first == LLONG_MAX) continue;
vector<int> aaa;
aaa.push_back(dp[i][k].first);
aaa.push_back(dp[i][k].second);
aaa.push_back(dp[i - 1][k - j - 1].first + crntsum);
if ((int)vals[i + 1].size() - 1 != j) {
aaa.push_back(dp[i - 1][k - j - 1].first + crntsum - vals[i + 1][j] + vals[i + 1][j + 1]);
}
if (dp[i - 1][k - j - 1].second != LLONG_MAX) {
aaa.push_back(dp[i - 1][k - j - 1].second + crntsum);
}
sort(aaa.begin(), aaa.end());
dp[i][k] = {aaa[0], aaa[1]};
}
}
for (int j = 1; j <= n; j++) {
vector<int> aaa;
aaa.push_back(dp[i][j].first);
aaa.push_back(dp[i][j].second);
aaa.push_back(dp[i - 1][j].first);
aaa.push_back(dp[i - 1][j].second);
sort(aaa.begin(), aaa.end());
dp[i][j] = {aaa[0], aaa[1]};
}
}
for (int i = n; i >= 0; i--) {
if (dp.back()[i].first != LLONG_MAX) {
cout << i << ' ' << dp.back()[i].first << '\n';
k--;
if (k == 0)
return 0;
}
if (dp.back()[i].second != LLONG_MAX) {
cout << i << ' ' << dp.back()[i].second << '\n';
k--;
if (k == 0)
return 0;
}
}
}
else {
vector<pair<int, int>> anss;
for (int i = 0; i < (1LL << n); i++) {
pair<int, int> crnt = {0, 0};
bool works = true;
for (int j = 0; j < n; j++) {
if ((i & (1LL << j))) {
if (-crnt.first < valss[j].first) {
crnt.first--;
crnt.second += valss[j].second;
}
else {
works = false;
break;
}
}
}
if (!works) continue;
anss.push_back(crnt);
}
sort(anss.begin(), anss.end());
for (int i = 0; i < k; i++) {
cout << -anss[i].first << ' ' << anss[i].second << '\n';
}
}
}
