#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define int ll
#define uint ull
pair<int, int> prods[20 + 5];
int n, k;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> prods[i].second >> prods[i].first;
sort(prods, prods + n);
uint mask = (1 << n) - 1;
uint perm = 0;
vector<pair<int, int>> solns;
do {
int cost = 0;
int time = 1;
int bought = 0;
for (int i = 0; i < n; ++i) {
if (((perm >> i) & 1) == 0) continue;
if (prods[i].first < time) continue;
time++;
bought++;
cost += prods[i].second;
}
if (bought == __builtin_popcountll(perm)) {
solns.emplace_back(pair{-bought, cost});
}
perm = (perm - mask) & mask;
} while (perm);
sort(solns.begin(), solns.end());
for (int i = 0; i < k; ++i) {
cout << -solns[i].first << ' ' << solns[i].second << '\n';
}
}
