#include<bits/stdc++.h>
using namespace std;
const int N = 2000 + 10;
int n, k;
struct Product {
int w, d;
friend istream& operator >> (istream& is, Product& rhs) {
return is >> rhs.w >> rhs.d;
}
} p[N];
multiset<pair<int, long long>> s[N];
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> p[i];
sort(p + 1, p + n + 1, [&](const auto& a, const auto& b) {
return a.d < b.d;
});
s[0] = {{0, 0}};
for (int i = 1; i <= n; ++i) {
const auto& [w, d] = p[i];
for (int j = d; j >= 1; --j) {
for (const auto& [cnt, cost] : s[j - 1]) {
s[j].insert({cnt + 1, cost - w});
if ((int)s[j].size() > k) s[j].erase(s[j].begin());
}
}
}
vector<pair<int, long long>> answer(1);
for (int i = 1; i <= n; ++i)
answer.insert(answer.end(), s[i].begin(), s[i].end());
sort(answer.begin(), answer.end(), greater<>());
for (int i = 0; i < k; ++i)
cout << answer[i].first << " " << -answer[i].second << "\n";
}
