#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=2005;
#define f first
#define s second
const string br="617283";
struct cmp{
bool operator()(const pair<ll,ll> &a,const pair<ll,ll> &b)const{
if(a.f==b.f)return a.s<b.s;
return a.f>b.f;
}
};
multiset<pair<ll,ll>,cmp>dp[N][N];
ll n,k,a[N],d[N],p[N];
void upd(multiset<pair<ll,ll>,cmp> &a){
while(a.size()>k){
auto it=(--a.end());
a.erase(it);
}
}bool comp(ll a,ll b){
return d[a]<d[b];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(ll i=1;i<=n;i++){
cin>>a[i]>>d[i];
p[i]=i;
}
sort(p+1,p+1+n,&comp);
dp[0][0].insert({0,0});
for(ll i=1;i<=n;i++){
dp[i][0]=dp[i-1][0];
for(ll j=1;j<=n;j++){
dp[i][j]=dp[i-1][j];
for(auto [cnt,w]:dp[i-1][j-1]){
if(cnt+1>d[p[i]])continue;
dp[i][j].insert({cnt+1,w+a[p[i]]});
}
upd(dp[i][j]);
}
}
for(ll i=n;i>=0;i--){
for(auto [cnt,w]:dp[n][i]){
cout<<cnt<<' '<<w<<'\n';
k--;
if(!k)return 0;
}
}
}
