#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
vector<ll>V[2007];
priority_queue<pair<pair<int,ll>,pair<int,int>>>Q;
vector<pair<pair<int,ll>,pair<int,int>>>best;
vector<ll>ord;
void add(int i,int j)
{
ll w=best[j].st.nd;
int x=best[j].nd.st,y=best[j].nd.nd,s=best[j].st.st;
if(x<sz(ord))
{
if(y<sz(V[i]))
{
if(ord[x]>V[i][y])
{
Q.push({{s+1,w+ord[x]},{x+y+1,j}});
best[j].nd.st++;
}
else
{
Q.push({{s+1,w+V[i][y]},{x+y+1,j}});
best[j].nd.nd++;
}
}
else
{
Q.push({{s+1,w+ord[x]},{x+y+1,j}});
best[j].nd.st++;
}
}
else if(y<sz(V[i]))
{
Q.push({{s+1,w+V[i][y]},{x+y+1,j}});
best[j].nd.nd++;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k,d;
ll w;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>w>>d;
V[d].pb(-w);
}
best.pb({{0,0},{0,0}});
for(int i=n;i>0;i--)
{
sort(all(V[i]),greater<ll>());
while(sz(Q)>0) Q.pop();
vector<pair<pair<int,ll>,pair<int,int>>>nbest;
for(int j=0;j<sz(best);j++)
{
Q.push({{best[j].st.st,best[j].st.nd},{best[j].nd.st,-1}});
add(i,j);
}
while(sz(Q)>0&&sz(nbest)<k)
{
ll w=Q.top().st.nd;
int x=Q.top().nd.st,j=Q.top().nd.nd,s=Q.top().st.st;
Q.pop();
nbest.pb({{s,w},{x,0}});
if(j!=-1) add(i,j);
}
best=nbest;
for(auto x:V[i]) ord.pb(x);
sort(all(ord),greater<ll>());
}
for(auto x:best) cout<<x.st.st<<" "<<-x.st.nd<<endl;
return 0;
}
