#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919810364364
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, a[20][20];
int d[(1 << 16)];
vector<int> vec;

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> a[i][j];
	for (int i = 1; i < (1 << n); i++) {
		vec.clear();
		for (int j = 0; j < n; j++)if (i&(1 << j))vec.push_back(j);
		int m = (int)vec.size();
		int ma = 0;
		for (int j = 0; j < (int)vec.size(); j++)for (int k = j + 1; k < (int)vec.size(); k++)ma += a[vec[j]][vec[k]];
		for (int j = 0; j < (1 << m); j++) {
			int cnt = 0;
			for (int k = 0; k < m; k++)if (j&(1 << k))cnt += (1 << vec[k]);
			ma = max(ma, d[cnt] + d[i - cnt]);
		}
		d[i] = ma;
	}
	cout << d[(1 << n) - 1] << endl;
}
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl
#define debugArray(x, n)                                      \
  cerr << __LINE__ << ": " << #x << " = {";                   \
  for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];                   \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int N;
  cin >> N;
  long long L[N], R[N];
  for (int i = 0; i < N; i++) cin >> L[i] >> R[i];
  int idx[N];
  iota(idx, idx + N, 0);
  // debugArray(idx, N);
  auto step = [&]() {
    long long leftl[N + 1], leftr[N + 1], rightl[N + 1], rightr[N + 1];
    leftl[0] = 0, leftr[0] = INT_MAX;
    for (int i = 0; i < N; i++) {
      int j = idx[i];
      leftl[i + 1] = max(leftl[i], L[j]);
      leftr[i + 1] = min(leftr[i], R[j]);
    }
    rightl[N] = 0, rightr[N] = INT_MAX;
    for (int i = N - 1; i >= 0; i--) {
      int j = idx[i];
      rightl[i] = max(rightl[i + 1], L[j]);
      rightr[i] = min(rightr[i + 1], R[j]);
    }
    // debugArray(leftl, N + 1);
    // debugArray(leftr, N + 1);
    // debugArray(rightl, N + 1);
    // debugArray(rightr, N + 1);
    long long ret = 0;
    for (int i = 0; i < N - 1; i++) {
      ret = max(ret, max(0ll, leftr[i + 1] - leftl[i + 1] + 1)
                         + max(0ll, rightr[i + 1] - rightl[i + 1] + 1));
    }
    for (int i = 0; i < N; i++) {
      int j = idx[i];
      int ll = max(leftl[i], rightl[i + 1]);
      int rr = min(leftr[i], rightr[i + 1]);
      ret = max(ret, max(0, rr - ll + 1) + R[j] - L[j] + 1);
    }
    return ret;
  };
  long long ans = 0;
  sort(idx, idx + N,
       [&](int l, int r) { return L[l] == L[r] ? R[l] > R[r] : L[l] < L[r]; });
  ans = max(ans, step());
  sort(idx, idx + N,
       [&](int l, int r) { return R[l] == R[r] ? L[l] > L[r] : R[l] < R[r]; });
  ans = max(ans, step());
  cout << ans << '\n';
  return 0;
}
