#include <bits/stdc++.h>
using namespace std;
const int M = 32;
int n;
int x[16]; // x[i] in 1 .. M
int y[16];
int F[M+1];
int f(int x){return F[x] == x ? x : F[x] = f(F[x]);}
bool important[M+1];
int flux[M+1]; // from i to i+1
void merge(int a, int b)
{
int fa = f(a), fb = f(b);
if(fa != fb)
F[fa] = fb;
}
struct edge
{
int a, b, len;
bool operator <(const edge that)const
{
return len < that.len;
}
};
int solve()
{
for(int i = 1; i <= M; i++)
F[i] = i;
memset(flux, 0, sizeof(flux));
memset(important, false, sizeof(important));
for(int i = 0; i < n; i++)
{
merge(x[i], y[i]);
important[x[i]] = important[y[i]] = true;
if(x[i] < y[i])
for(int j = x[i]; j < y[i]; j++)
flux[j] ++;
if(x[i] > y[i])
for(int j = y[i]; j < x[i]; j++)
flux[j] --;
}
int ans = 0;
for(int i = 1; i < M; i++)
{
if(flux[i] < 1)
merge(i, i+1);
if(flux[i] > 1)
{
ans += flux[i] - 1;
merge(i, i+1);
}
}
vector <edge> lis;
int prevImportant = -1;
for(int i = 1; i <= M; i++)
if(important[i])
{
if(prevImportant != -1)
{
if(f(prevImportant) != f(i))
{
edge e;
e.a = prevImportant;
e.b = i;
e.len = i - prevImportant;
lis.push_back(e);
}
}
prevImportant = i;
}
sort(lis.begin(), lis.end());
for(int i = 0; i < lis.size(); i++)
{
if(f(lis[i].a) != f(lis[i].b))
{
ans += lis[i].len;
merge(lis[i].a, lis[i].b);
}
}
return ans;
}
int dp[1<<16][16];
int dodp(int mask, int last)
{
if(mask == (1<<n)-1) return 0;
int &ret = dp[mask][last];
if(ret != -1) return ret;
ret = 1000000000;
for(int i = 0; i < n; i++)
if((mask & (1<<i)) == 0)
ret = min(ret, dodp(mask | (1<<i) , i) + max(0, y[last] - x[i]));
return ret;
}
int bruteforce()
{
memset(dp, 0xff, sizeof(dp));
int ret = 1000000000;
for(int i = 0; i < n; i++)
ret = min(ret, dodp(1<<i, i));
return ret;
}
int MAIN()
{
srand((unsigned)time(NULL));
int nCorrect = 0;
for(int testCase = 1; testCase <= 500; testCase ++)
{
/*cin >> n;
for(int i = 0; i < n; i++)
cin >> x[i];
for(int i = 0; i < n; i++)
cin >> y[i];*/
n = rand() % 16 + 1;
for(int i = 0; i < n; i++)
{
x[i] = rand() % 32 + 1;
y[i] = rand() % 32 + 1;
}
int ansBF = bruteforce();
int ans = solve();
if(ansBF != ans) cout << "ERROR" << endl;
else nCorrect ++;
}
cout << nCorrect << " correct " << endl;
return 0;
}
int main()
{
int start = clock();
#ifdef LOCAL_TEST
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios :: sync_with_stdio(false);
cout << fixed << setprecision(16);
int ret = MAIN();
#ifdef LOCAL_TEST
cout << "[Finished in " << clock() - start << " ms]" << endl;
#endif
return ret;
}