#include "railroad.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
typedef long long ll;
#define ar array
const ll inf = 1e18;
namespace S1{
const int N = 16;
ll dp[1 << N][N];
ll solve(vector<int> s, vector<int> t){
int n = s.size();
memset(dp, 15, sizeof dp);
for(int i=0;i<n;i++){
dp[(1 << i)][i] = 0;
}
for(int mask=1;mask < (1 << n);mask++){
for(int i=0;i<n;i++){
if(mask >> i & 1){
for(int j=0;j<n;j++){
if((mask >> j & 1) && i != j){
dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + max(0, t[j] - s[i]));
}
}
}
}
}
ll res = inf;
for(int i=0;i<n;i++){
res = min(res, dp[(1 << n) - 1][i]);
}
return res;
}
};
namespace S2{
const int N = 4e5 + 5;
vector<int> edges[N], G[N], ss;
int dp[N], used[N], tin[N], fup[N], t;
int cmp[N], last, cnt[N];
void dfs(int u){
used[u] = 1, tin[u] = fup[u] = ++t;
ss.push_back(u);
for(auto x : edges[u]){
if(used[x]){
if(cmp[x]) continue;
fup[u] = min(fup[u], tin[x]);
} else {
dfs(x);
fup[u] = min(fup[u], fup[x]);
}
}
if(tin[u] == fup[u]){
int v; ++last;
do{
v = ss.back(); ss.pop_back();
cmp[v] = last;
}while(v != u);
}
}
ll solve(vector<int> s, vector<int> t){
int n = s.size();
vector<ar<int, 2>> a(n);
for(int i=0;i<n;i++) a[i] = {s[i], t[i]};
sort(a.begin(), a.end());
for(int i=0;i<n;i++){
if(i + 1 < n) edges[i + n].push_back(i + n + 1);
edges[i + n].push_back(i);
int j = lower_bound(a.begin(), a.end(), (ar<int, 2>){a[i][1], -1}) - a.begin();
if(j < n) edges[i].push_back(j + n);
}
for(int i=0;i<n + n;i++){
if(used[i]) continue;
dfs(i);
}
for(int i=0;i<n + n;i++){
cnt[cmp[i]] += (i < n);
for(auto x : edges[i]){
if(cmp[i] != cmp[x]){
G[cmp[i]].push_back(cmp[x]);
}
}
}
t.clear();
memset(used, 0, sizeof used);
function<void(int)> dfs = [&](int u){
used[u] = 1;
for(auto x : G[u]){
if(used[x]) continue;
dfs(x);
}
t.push_back(u);
};
for(int i=1;i<=last;i++){
if(used[i]) continue;
dfs(i);
}
for(auto u : t){
dp[u] = cnt[u];
for(auto x : G[u]){
dp[u] = max(dp[u], dp[x] + cnt[u]);
}
}
if(dp[t.back()] == n) return 1;
return 0;
}
};
/*
4
1 7
4 3
5 8
6 6
*/
ll plan_roller_coaster(vector<int> s, vector<int> t) {
int n = s.size();
if(n <= 16){
return S1::solve(s, t);
}
return S2::solve(s, t);
}
