Problem: You are given a set of n segments on a line [L_i; R_i]. All 2n segment endpoints are pairwise distinct integers.

The set is laminar — any two segments are either disjoint or one of them contains the other.

Choose a non-empty subsegment [l_i, r_i] with integer endpoints in each segment (L_i ≤ l_i < r_i ≤ R_i) in such a way that no two subsegments intersect (they are allowed to have common endpoints though) and the sum of their lengths (∑_{i=1}^n r_i - l_i) is maximized.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^3) — the number of segments.

The i-th of the next n lines contains two integers L_i and R_i (0 ≤ L_i < R_i ≤ 10^9) — the endpoints of the i-th segment.

All the given 2n segment endpoints are distinct. The set of segments is laminar.

Output

On the first line, output the maximum possible sum of subsegment lengths.

On the i-th of the next n lines, output two integers l_i and r_i (L_i ≤ l_i < r_i ≤ R_i), denoting the chosen subsegment of the i-th segment.

Example

Input


4
1 10
2 3
5 9
6 7


Output


7
3 6
2 3
7 9
6 7

Note

The example input and the example output are illustrated below. <image> <image>

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

const int maxn=2005;
int n,m,s,top,ans;
int ord[maxn],st[maxn],sz[maxn],dp[maxn][maxn][2][2],nsz[maxn],ndp[maxn][maxn][2][2],prv[maxn],mat[maxn];
pair<pair<int,int>,int>nseg[maxn*3];
pair<int,int>seg[maxn],aseg[maxn];
vector<int>edge[maxn];
bool used[maxn];

bool cmp(int a,int b){
	if(seg[a].second!=seg[b].second)return seg[a].second<seg[b].second;
	return seg[a].first>seg[b].first;
}
void ckmax(int &a,int b){
	if(b>a)a=b;
}

void dfs1(int x,int d){
	if(edge[x].empty()){
		dp[x][0][0][0]=seg[x].second-seg[x].first;
		return;
	}
	int z=0;
	for(int i=0;i<int(edge[x].size());i++){
		int y=edge[x][i];
		dfs1(y,d+1);
		if(!z){
			for(int j=0;j<=sz[y];j++)for(int a=0;a<2;a++)for(int b=0;b<2;b++)
				ndp[y][j][a][b]=dp[y][j][a][b];
			nsz[y]=sz[y];
		}
		else{
			int len=seg[y].first-seg[z].second;
			for(int j=0;j<=sz[y];j++)for(int a=0;a<2;a++)for(int b=0;b<2;b++)if(dp[y][j][a][b])
				for(int k=0;k<=nsz[z];k++)for(int c=0;c<2;c++)for(int d=0;d<2;d++)if(ndp[z][k][c][d]){
					if(!d&&!a)ckmax(ndp[y][j+k][c][b],dp[y][j][a][b]+ndp[z][k][c][d]);
					ckmax(ndp[y][j+k+1-d-a][c][b],dp[y][j][a][b]+ndp[z][k][c][d]+len);
				}
			nsz[y]=nsz[z]+sz[y]+1;
		}
		prv[y]=z;
		z=y;
	}
	int lenl=seg[edge[x][0]].first-seg[x].first,lenr=seg[x].second-seg[z].second;
	for(int j=0;j<=nsz[z];j++)for(int a=0;a<2;a++)for(int b=0;b<2;b++)if(ndp[z][j][a][b])
		for(int c=0;c<2;c++)for(int d=0;d<2;d++)for(int e=max(a,c);e<2;e++)for(int f=max(b,d);f<2;f++){
			if(j+e+f-a-b>0)
				ckmax(dp[x][j+e+f-a-b-1][c][d],ndp[z][j][a][b]+e*lenl+f*lenr);
		}
	dp[x][0][0][1]=dp[x][0][1][0]=dp[x][0][1][1]=dp[x][1][1][1]=0;
	sz[x]=min(nsz[z]+1,d);
}

void dfs2(int x,int j,int a,int b){
	if(edge[x].empty()){
		assert(j==0&&a==0&&b==0);
		nseg[++m]=make_pair(seg[x],0);
		return;
	}
	int z=edge[x].back();
	int lenl=seg[edge[x][0]].first-seg[x].first,lenr=seg[x].second-seg[z].second;
	bool fnd=false;
	for(int c=0;c<2;c++)for(int d=0;d<2;d++)for(int e=max(a,c);e<2;e++)for(int f=max(b,d);f<2;f++){
		if(fnd)break;
		int k=j+c+d+1-e-f;
		if(k>=0&&k<=nsz[z]&&ndp[z][k][c][d]&&ndp[z][k][c][d]+e*lenl+f*lenr==dp[x][j][a][b]){
			if(e)nseg[++m]=make_pair(make_pair(seg[x].first,seg[edge[x][0]].first),a);
			if(f)nseg[++m]=make_pair(make_pair(seg[z].second,seg[x].second),d); 
			j=k;a=c;b=d;
			fnd=true;
		}
	}
	while(prv[z]){
		int y=z;
		z=prv[z];
		int len=seg[y].first-seg[z].second;
		bool fnd=false;
		for(int k=0;k<=nsz[z];k++)for(int c=0;c<2;c++)for(int d=0;d<2;d++)if(ndp[z][k][a][c]){
			if(fnd)break;
			int jj=j-k;
			if(!c&&!d&&jj>=0&&jj<=sz[y]&&dp[y][jj][d][b]&&dp[y][jj][d][b]+ndp[z][k][a][c]==ndp[y][j][a][b]){
				dfs2(y,jj,d,b);
				j=k;b=c;
				fnd=true;
				break;
			}
			jj=j+c+d-1-k;
			if(jj>=0&&jj<=sz[y]&&dp[y][jj][d][b]&&dp[y][jj][d][b]+ndp[z][k][a][c]+len==ndp[y][j][a][b]){
				nseg[++m]=make_pair(make_pair(seg[z].second,seg[y].first),c);
				dfs2(y,jj,d,b);
				j=k;b=c;
				fnd=true;
				break;
			}
		}
	}
	dfs2(z,j,a,b);
}
void dfs3(int x){
	for(int i=0;i<int(edge[x].size());i++)
		dfs3(edge[x][i]);
	for(int j=1;j<=s;j++)if(!used[j]&&aseg[j].first>=seg[x].first&&aseg[j].second<=seg[x].second){
		mat[x]=j;
		used[j]=true;
		break;
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&seg[i].first,&seg[i].second),ord[i]=i;
	sort(ord+1,ord+1+n,cmp);
	for(int i=1;i<=n;i++){
		int x=ord[i];
		while(top&&seg[st[top]].first>=seg[x].first)
			edge[x].push_back(st[top--]);
		reverse(edge[x].begin(),edge[x].end());
		st[++top]=x;
	}
	for(int i=1;i<=top;i++){
		dfs1(st[i],0);
		ans+=dp[st[i]][0][0][0];
		dfs2(st[i],0,0,0);
	}
	sort(nseg+1,nseg+1+m);
	for(int i=1;i<=m;i++){
		if(nseg[i].second==1)
			assert(aseg[s].second==nseg[i].first.first),aseg[s].second=nseg[i].first.second;
		else aseg[++s]=nseg[i].first;
	} 
	for(int i=1;i<=top;i++)
		dfs3(st[i]);
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)printf("%d %d\n",aseg[mat[i]].first,aseg[mat[i]].second);
	return 0;
}