//OccDreamer
#include<bits/stdc++.h>

#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define OccDreamer
#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(ll x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(ll x){write(x), putchar(32);}
	inline void eprint(ll x){write(x), putchar(10);}
}using namespace IO;

const int MAXN = 2005;

int n, k, poss;

struct P{
	int w, d;
	inline bool friend operator < (const P &x, const P &y){return x.d==y.d?x.w<y.w:x.d<y.d;}
}c[MAXN];

struct dp{
	int num; ll val;	
	inline dp friend operator + (const dp &x, const dp &y){return dp{x.num+y.num,x.val+y.val};}
	inline bool friend operator < (const dp &x, const dp &y){
		return x.num==y.num?x.val<y.val:x.num>y.num;	
	}
}f[MAXN][MAXN];

inline bool comp(dp x, dp y){
	return (x+f[pos][x.num])<(y+f[pos][y.num]);
}

signed main(){
	n=read(), k=read();
	for(int i=1;i<=n;++i) c[i].w=read(), c[i].d=read();
	sort(c+1,c+1+n);
	for(int i=n;i>=1;--i){
		for(int j=n;j>=0;--j){
			f[i][j]=min(f[i][j],f[i+1][j]); f[i][j]=min(f[i][j+1],f[i][j]);
			if(c[i].d>j) f[i][j]=min(f[i][j],f[i+1][j+1]+dp{1,c[i].w});	
		//cerr << "dp:" << i << ' ' << j << ' ' << f[i][j].num << ' ' << f[i][j].val << endl;
		}
	}
	vc<dp> now; now.pb(dp{0,0});
	for(int i=1;i<=n;++i){
		vc<dp> S;
		//cerr << i << ' ' << now[0].num << ' ' << now[0].val << endl;
		for(auto j:now){
			S.pb(j);
			if(c[i].d>j.num) S.pb(dp{j.num+1,j.val+c[i].w});	
		}
		poss=i+1;
		sort(S.begin(),S.end(),comp);
		int o=min((long long)(S.size()),k); now.clear();
		for(int j=0;j<o;++j) now.pb(S[j]);
	}
	sort(now.begin(),now.end());
	for(auto i:now) sprint(i.num), eprint(i.val);
	return 0;
}
/*
9 1
539032129 4
539032129 4
539032130 4
539031219 4
539019129 4
539032129 4
539034123 4
539042939 4
539524354 4
*/

answer.code: In function ‘bool comp(dp, dp)’:
answer.code:62:21: error: ‘pos’ was not declared in this scope; did you mean ‘pow’?
   62 |         return (x+f[pos][x.num])<(y+f[pos][y.num]);
      |                     ^~~
      |                     pow