#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<vector<int>>> dp(n, vector<vector<int>>(n + 1, vector<int>(K, LLONG_MAX)));
for (int i = 0; i < n; i++) {
if (i == 0) {
dp[0][0][0] = 0;
for (int j = 0; j < min(K, (int)vals[1].size()); j++) {
dp[0][1][j] = vals[1][j];
}
continue;
}
vector<pair<int, int>> crntsum = {{0, -1}};
dp[i][0][0] = 0;
for (int j = 0; j < (int)vals[i + 1].size(); j++) {
auto acrntsum = crntsum;
crntsum.clear();
for (auto l : acrntsum) {
for (int k = l.second + 1; k < (int) vals[i + 1].size(); k++) {
crntsum.push_back({l.first + vals[i + 1][k], k});
}
}
sort(crntsum.begin(), crntsum.end());
while ((int)crntsum.size() > K)
crntsum.pop_back();
for (int k = j + 1; k <= i + 1; k++) {
vector<int> aaa = dp[i][k];
for (int l = 0; l < K; l++) {
if (dp[i - 1][k - j - 1][l] == LLONG_MAX) break;
for (int m = 0; m < (int)crntsum.size(); m++) {
aaa.push_back(dp[i - 1][k - j - 1][l] + crntsum[m].first);
}
}
sort(aaa.begin(), aaa.end());
for (int l = 0; l < K; l++) {
dp[i][k][l] = aaa[l];
}
}
}
for (int j = 1; j <= n; j++) {
vector<int> aaa = dp[i][j];
for (int k = 0; k < K; k++)
aaa.push_back(dp[i - 1][j][k]);
sort(aaa.begin(), aaa.end());
for (int k = 0; k < K; k++)
dp[i][j][k] = aaa[k];
}
}
int kkk = K;
for (int i = n; i >= 0; i--) {
for (int j = 0; j < K; j++) {
if (dp.back()[i][j] == LLONG_MAX) break;
cout << i << ' ' << dp.back()[i][j] << '\n';
kkk--;
if (kkk == 0)
return 0;
}
}
}
