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>

#define ln                 '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (__typeof(to) i = 0; i < to; ++i)
#define cont(i, to)        for (__typeof(to) i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (__typeof(to) i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 2e3, ssz = 2.5e7, inf = 0x3f3f3f3f;
int n, ans, siz[nsz + 5];
int dp[nsz + 5][nsz + 5][2][2], id[nsz + 5][nsz + 5][2][2];
vector<int> g[nsz + 5];

struct segment {
	int l, r, id;
	
	segment() {}
	segment(int l, int r, int id = -1): l(l), r(r), id(id) {}
	
	segment inline operator & (const segment &b) const {
		return segment(max(l, b.l), min(r, b.r));
	}
	
	bool inline operator == (const segment &b) const {
		return l == b.l && r == b.r;
	}
	
	bool inline operator < (const segment &b) const {
		return l != b.l ? l < b.l : r < b.r;
	}
};
segment a[nsz + 5], res[nsz + 5];

struct state {
	int fm1, fm2;
	char f;
	bool p, s;
	
	state() {}
	state(bool p, bool s, char f, int fm1 = -1, int fm2 = -1): p(p), s(s), f(f), fm1(fm1), fm2(fm2) {}
};
vector<state> states;

struct cat {
	bool f1, f2;
	int l, r;
	
	cat() {}
	cat(int l, int r, bool f1, bool f2): l(l), r(r), f1(f1), f2(f2) {}
};

bool inline upd(int &a, int b) {
	if (a < b) { a = b; return 1; }
	return 0;
}

void inline ins(int &id, const state &s) {
	if (id == -1) id = states.size(), states.push_back(s);
	else states[id] = s;
}

void dfs(int u) {
	if (g[u].size() == 0) {
		siz[u] = 1;
		int l = a[u].l, r = a[u].r, len = r - l;
		dp[u][0][0][0] = len, ins(id[u][0][0][0], state(0, 0, 1));
		return;
	}
	static int f[2][2 * nsz + 5][2][2], fm[2][2 * nsz + 5][2][2];
	for (int v : g[u]) dfs(v);
	memset(f, -inf, sizeof(f)), memset(fm, -1, sizeof(fm));
	int o = 0, x = 1, l = a[g[u].back()].r, r = a[u].r, len = r - l;
	siz[u] = g[u].size() > 0 ? int(g[u].size()) + 1 : 1;
	f[o][0][0][0] = 0, ins(fm[o][0][0][0], state(-1, -1, 0));
	loop (i, g[u].size()) {
		int v = g[u][i], l = !i ? a[u].l : a[g[u][i - 1]].r, r = a[v].l, len = r - l;
		circ (k1, 0, siz[u]) circ (k2, 0, siz[v]) {
			if (k1 + k2 > n) break;
			loop (p1, 2) loop (s1, 2) loop (p2, 2) loop (s2, 2) {
				int w1 = f[o][k1][p1][s1], w2 = dp[v][k2][p2][s2], nk = k1 + k2 + 1 - s1 - p2, np = !i ? 1 : p1;
				int id1 = fm[o][k1][p1][s1], id2 = id[v][k2][p2][s2];
				if (upd(f[x][k1 + k2][p1][s2], w1 + w2)) {
					ins(fm[x][k1 + k2][p1][s2], state(p1, s2, 0, id1, id2));
				}
				if (nk >= 0 && upd(f[x][nk][np][s2], w1 + len + w2)) {
					ins(fm[x][nk][np][s2], state(np, s2, 1, id1, id2));
				}
			}
		}
		siz[u] += siz[v], siz[u] = min(siz[u], n);
		swap(o, x), memset(f[x], -inf, sizeof(f[x])), memset(fm[x], -1, sizeof(fm[x]));
	}
	circ (k, 0, siz[u]) loop (p, 2) loop (s, 2) {
		int w = f[o][k][p][s], nk = k - s + 1, id = fm[o][k][p][s];
		if (upd(f[x][k][p][0], w)) {
			ins(fm[x][k][p][0], state(p, 0, 0, id));
		}
		if (upd(f[x][nk][p][1], w + len)) {
			ins(fm[x][nk][p][1], state(p, 1, 1, id));
		}
	}
	loop (k, siz[u]) loop (p, 2) loop (s, 2) {
		if (upd(dp[u][k][p][s], f[x][k + 1][p][s])) {
			id[u][k][p][s] = fm[x][k + 1][p][s];
		}
		circ (np, 0, p) circ (ns, 0, s) if (upd(dp[u][k][np][ns], dp[u][k][p][s])) {
			ins(id[u][k][np][ns], state(np, ns, 2, id[u][k][p][s]));
		}
	}
	dp[u][0][0][1] = dp[u][0][1][0] = dp[u][0][1][1] = dp[u][1][1][1] = -inf;
	id[u][0][0][1] = id[u][0][1][0] = id[u][0][1][1] = id[u][1][1][1] = -1;
}

void go(int id, int u, int k, vector<cat> &c) {
	if (k < 0) return;
	state s = states[id];
	char f = s.f;
	int p1 = s.fm1, p2 = s.fm2, l, r;
	int f1 = p1 != -1 && states[p1].fm1 == -1 ? s.p : 0, f2 = s.s;
	if (g[u].size() == 0) {
		l = a[u].l, r = a[u].r;
	} else if (k == 0) {
		l = a[u].l, r = a[g[u][0]].l;
	} else if (k == g[u].size()) {
		l = a[g[u].back()].r, r = a[u].r;
	} else {
		l = a[g[u][k - 1]].r, r = a[g[u][k]].l;
	}
	if (p1 != -1) go(p1, u, k - (f != 2), c);
	if (f == 1) c.push_back(cat(l, r, f1, f2));
	if (f == 2) c.back().f1 &= f1, c.back().f2 &= f2;
	if (p2 != -1) go(p2, g[u][k], g[g[u][k]].size(), c);
}

void divide(int u, vector<segment> &s) {
	for (int v : g[u]) divide(v, s);
	loop (i, s.size()) {
		if ((s[i] & a[u]) == s[i]) {
			res[a[u].id] = s[i];
			s.erase(s.begin() + i);
			break;
		}
	}
}

void inline back_track(int u) {
	vector<cat> c;
	vector<segment> s;
	go(id[u][0][0][0], u, g[u].size(), c);
	loop (i, c.size()) {
		int l = c[i].l, r = c[i].r;
		if (s.size() && s.back().r == l && c[i].f1) s.back().r = r;
		else if (s.size() && i && c[i - 1].f2) s.back().r = r;
		else s.push_back(segment(l, r));
	}
	divide(u, s);
}

void inline init() {
	a[0] = segment(-inf, +inf, 0);
	sort(a + 1, a + n + 1);
	int sz = 0;
	static int stk[nsz + 5];
	cont (i, n) {
		int l = a[i].l, r = a[i].r;
		for (; sz && a[stk[sz]].r < l; --sz);
		g[stk[sz]].push_back(i);
		stk[++sz] = i;
	}
}

void inline solve() {
	memset(dp, -inf, sizeof(dp)), memset(id, -1, sizeof(id));
	states.reserve(ssz);
	for (int u : g[0]) {
		dfs(u);
		ans += dp[u][0][0][0];
		back_track(u);
	}
}

int main() {
	scanf("%d", &n);
	cont (i, n) scanf("%d%d", &a[i].l, &a[i].r), a[i].id = i;
	init();
	solve();
	printf("%d\n", ans);
	cont (i, n) printf("%d %d\n", res[i].l, res[i].r);
}