#include <iostream>
#include <algorithm>
using namespace std;
int n,k,head[100005],vis[100005],t,len,mt;
long long ans;
struct node
{
	int t,d,nex;
	int f=0;
}edge[100005],a[100005],dui[200005];
void add(node xxx)
{
	edge[++len].d=xxx.d;
	edge[len].nex=head[xxx.t];
	edge[len].t=xxx.t;
	head[xxx.t]=len;
	mt=max(xxx.t,mt);
}
void du(int cur,int val){
	if(cur>n)return;
	//cout<<dui[1].f<<endl;
	du(cur*2,val);
	if(dui[cur].d+dui[cur].f*val<dui[cur*2].d+dui[cur*2].f*val)
	{
		swap(dui[cur],dui[cur*2]);
	}
	du(cur*2+1,val);
	//cout<<dui[1].f<<endl;
	if(dui[cur].d+dui[cur].f*val<dui[cur*2+1].d+dui[cur*2+1].f*val)
	{
		swap(dui[cur],dui[cur*2+1]);
	}
}
bool cmp(node a,node b)
{
	return a.d<b.d;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i].t>>a[i].d;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)add(a[i]);
	for(int i=1;i<=mt;i++){dui[i]=edge[head[i]];dui[i].f=1;}
	du(1,0);
	for(int i=1;i<=k;i++)
	{
		if(dui[1].f!=0){t++;}
		ans+=dui[1].d+dui[1].f*(t+t+1);
		dui[1].f=0;
		cout<<edge[head[dui[i].t]].t<<" "<<edge[head[dui[i].t]].d<<endl;
		head[dui[i].t]=edge[head[dui[i].t]].nex;
		dui[1].d=edge[head[dui[i].t]].d;
		//cout<<dui[1].f<<" "; 
		du(1,t+t+1);
		//cout<<dui[1].f<<endl;
	}
	cout<<ans;
}
/*
7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5
*/

思路：sort排->链星->堆