#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];
ll n,k,a[N],d[N];
void upd(multiset<pair<ll,ll>,cmp> &a){
while(a.size()>2*k){
auto it=(--a.end());
a.erase(it);
}
}
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];
}
dp[0].insert({0,0});
for(ll i=1;i<=n;i++){
dp[i]=dp[i-1];
for(auto [cnt,w]:dp[i-1]){
if(cnt+1>d[i])continue;
dp[i].insert({cnt+1,w+a[i]});
}
// upd(dp[i]);
}
for(auto [cnt,w]:dp[n]){
cout<<cnt<<' '<<w<<'\n';
k--;
if(!k)break;
}
}
