#include <bits/stdc++.h>
using namespace std;
#define int long long
pair<int, long long> solve(vector<pair<int, int>> a, int d) {
priority_queue<int> taken;
long long ans = 0;
for (int i = 0; i < (int)a.size(); i++) {
if (i == d) continue;
//case 1:
if ((int)taken.size() < a[i].first) {
taken.push(a[i].second);
ans += a[i].second;
}
else {
//consider to throw away or not
if (a[i].second < taken.top()) {
ans -= taken.top();
taken.pop();
ans += a[i].second;
taken.push(a[i].second);
}
}
}
return {(int) taken.size(), ans} ;
}
bool comp(pair<int, int> x, pair<int, int> y) {
if (x.first != y.first) return x.first > y.first;
return x.second < y.second;
};
signed main() {
int n; cin >> n;
int count; cin >> count;
if (count == 0) return 0;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) cin >> a[i].second >> a[i].first; //cost, time
sort(a.begin(), a.end());
if (n <= 20) {
vector<pair<int, int>> poss;
for (int i = 0; i < (1<<n); i++) {
int total1 = 0, total2 = 0; int possible = 1;
for (int j = 0; j < n; j++) {
if ((i&(1<<j)) > 0) {
total1 += 1;
total2 += a[j].second;
if (total1 > a[j].first) {
possible = 0;
break;
}
}
}
if (possible == 1) poss.push_back({total1, total2});
}
sort(poss.begin(), poss.end(), comp);
for (int i = 0; i < count; i++) cout << poss[i].first << ' ' << poss[i].second << '\n';
return 0;
}
else if (count <= 2) {
pair<int, long long> ans = solve(a, -1);
cout << ans.first << ' ' << ans.second << '\n';
if (count > 1) {
vector<pair<int, int>> tmp(n);
for (int i = 0; i < n; i++) {
tmp[i] = solve(a, i);
}
sort(tmp.begin(), tmp.end(), comp);
for (int i = 0; i < n; i++) {
if (tmp[i] != ans) {
cout << tmp[i].first << ' ' << tmp[i].second << '\n';
return 0;
}
}
}
}
else{
vector<int> dp[2][n+1];
dp[0][0] = {0};
for (int i = 1; i < n+1; i++) {
for (int j = 0; j < n+1; j++) {
if (j > a[i-1].first) continue;
//case 1: you take
//case 2: you DONT TAKE. whack it into a PQ.
//removing log factor from this :o
if (j == 0) {dp[1][j] = dp[0][j]; continue;}
int leftptr = 0;
int rightptr = 0;
for (int abc = 0; abc < count; abc++) {
//dp[0][j-1]+a[i-1].second vs dp[0][j].
if (leftptr == (int)dp[0][j-1].size()) {
if (rightptr != (int)dp[0][j].size()) {
dp[1][j].push_back(dp[0][j][rightptr]);
rightptr++;
}
}
else {
if (rightptr == (int) dp[0][j].size()) {
dp[1][j].push_back(dp[0][j-1][leftptr]+a[i-1].second);
leftptr++;
}
else {
if (dp[0][j-1][leftptr]+a[i-1].second < dp[0][j][rightptr]) {
dp[1][j].push_back(dp[0][j-1][leftptr]+a[i-1].second);
leftptr++;
}
else {
dp[1][j].push_back(dp[0][j][rightptr]);
rightptr++;
}
}
}
}
}
for (int j = 0; j < n+1; j++) dp[0][j] = dp[1][j];
for (int j = 0; j < n+1; j++) dp[1][j] = {};
}
int c = 0;
for (int i = n; i >= 0; i--) {
for (auto j:dp[0][i]) {
cout << i << ' ' << j << '\n';
c++;
if (c == count) return 0;
}
}
return 0;
}
}
