/*
For subtask 3, consider, for each rail, the prefix it can reach
4 2 1 0 -> doesn't work
3 1 1 1
4 2 2 0 -> works
3 2 1 1
4 3 1 0 -> works
4 2 1 1 -> doesn't work
2 2 4 0 -> doesn't work
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
vvll dp;
ll solve(const vi& s, const vi& t, ll n, ll mask, ll last) {
ll& ans = dp[mask][last];
if(ans == -1ll) {
ll mask_popcount = __popcount(mask);
if(mask_popcount <= 1ll) ans = 0ll;
else {
// Time to do it the normal, bitmask DP way
ll submask = mask ^ (1ll << last);
ans = INF(ll);
L(i, 0, n) {
if((submask >> i) & 0b1ll) {
// bit is set, recursive case time
ans = min(ans, solve(s, t, n, submask, i) + max((ll)t[i] - (ll)s[last], 0ll));
}
}
}
}
return ans;
}
ll plan_roller_coaster(vi s, vi t) {
ll n = s.size();
// Construct DP table
L(i, 0, 1ll << n) {
vll dpr(n, -1ll);
dp.push_back(dpr);
}
ll ans = INF(ll);
L(i, 0, n) {
ans = min(ans, solve(s, t, n, (1ll << n) - 1ll, i));
}
return ans;
}
#ifdef DEBUG
int main() {
int n;
cin >> n;
vi s(n, 0);
vi t(n, 0);
LI(i, 0, n) {
cin >> s[i] >> t[i];
}
cout << plan_roller_coaster(s, t) << endl;
}
#endif
