#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].insert({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;
  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";
}