#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
vector<pair<int, ll>> vec(n);
for (int i = 0; i < n; i++){
ll c; int t; cin >> c >> t;
vec[i] = {t, c};
}
sort(vec.begin(), vec.end());
vector<multiset<ll>> vals(n + 1);
vals[0].insert(0);
for (auto [t, c] : vec){
for (int i = t - 1; i >= 0; i--){
for (auto it = vals[i].begin(); it != vals[i].end(); it++){
if (vals[i + 1].size() == k && *(vals[i + 1].rbegin()) <= *it + c) break;
vals[i + 1].insert(*it + c);
if (vals[i + 1].size() > k) vals[i + 1].erase(prev(vals[i + 1].end()));
}
}
}
int cnt = 0;
for (int i = n; i >= 0; i--)
for (ll x : vals[i]){
cout << i << ' ' << x << '\n';
if (++cnt == k) return 0;
}
}
