#include using namespace std; #define rng(i,a,b) for(int i=int(a);i=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "< bool chmax(t&a,u b){if(a bool chmin(t&a,u b){if(b using vc=vector; template using vvc=vc>; using pi=pair; using vi=vc; //max weight matching for general graphs O(N^3) //init with an adjacency matrix g: use none for not-connected pairs. //ans = max weight matching of size 0,1,...,M. (M = max cardinality). //sol = solutions //verify yosupo, stress-tested(without int=ll) static const ll none=-infLL/3; struct maxweight{ static pi rev(pi x){return pi(x.b,x.a);} const vvc&g; const int n; vi idx,mt,bl,bs,tp; vc u,z; vc par,sf,ss; vvc me,ce; vvc cb; ll p(pi e){ if(e.a==e.b)return infLL; return u[e.a]+u[e.b]-g[e.a][e.b]*2; } void chme(pi&x,pi y){ if(p(x)>p(y))x=y; } void match(pi e){ int a=e.a,b=e.b; mt[a]=b; mt[b]=a; bs[bl[a]]=a; bs[bl[b]]=b; } void setb(int v,int b){ if(v&es){ int v=idx.back(); idx.pop_back(); ce[v]=es; cb[v].clear(); for(auto e:es) cb[v].pb(bl[e.a]); rep(i,n) me[v][i]=pi(-1,-1); for(auto c:cb[v]){ tp[c]=-2; setb(c,v); rep(i,n) chme(me[v][i],me[c][i]); } bs[v]=bs[cb[v][0]]; z[v]=0; labelS(v,par[cb[v][0]]); } vc path(int v){ vc es; while(par[bl[v]].a!=-1){ es.pb(par[bl[v]]); v=par[bl[v]].a; } return es; } bool SS(pi e){ vc x=path(e.a),y=path(e.b); while(x.size()&&y.size()&&x.back()==y.back()){ x.pop_back(); y.pop_back(); } vc es=x; reverse(all(es)); es.pb(e); for(auto f:y)es.pb(rev(f)); if(bl[es.front().a]==bl[es.back().b]){ make(es); return false; }else{ for(int i=0;i ans; vvc sol; maxweight(const vvc&gg):g(gg),n(g.size()), idx(n),mt(n,-1),bl(n),bs(n*2),tp(n*2,-1),u(n),z(n*2,0), par(n*2),sf(n),ss(n*2),me(n*2,vc(n)), ce(n*2),cb(n*2){ iota(all(idx),n); iota(all(bl),0); iota(all(bs),0); rng(i,n,n*2)tp[i]=-2; rep(i,n)rep(j,n)me[i][j]=pi(i,j); { ll mx=-infLL; rep(i,n)rep(j,i)chmax(mx,g[i][j]); fill(all(u),mx); } ans.pb(0); sol.pb(vi(n,-1)); rep(_,n/2){ rep(i,n*2)if(tp[i]!=-2) tp[i]=-1; fill(all(sf),pi(-1,-1)); rep(i,n)if(mt[i]==-1) labelS(bl[i],pi(-1,-1)); while(true){ ll d=infLL; pi e; rep(i,n){ int b=bl[i]; if(tp[b]==-1){ if(chmin(d,p(sf[i])))e=sf[i]; }else if(tp[b]==0){ if(chmin(d,p(ss[b])/2))e=ss[b]; }else if(n<=b){ if(chmin(d,z[b]/2))e=pi(b,-1); } } rep(i,n){ int t=tp[bl[i]]; if(t==0) u[i]-=d; else if(t==1) u[i]+=d; } rng(i,n,n*2) if(tp[i]==0) z[i]+=d*2; else if(tp[i]==1) z[i]-=d*2; if(e.b==-1){ expand(e.a,false); }else if(tp[bl[e.b]]==0){ if(SS(e)) break; }else{ int t=bl[e.b],m=mt[bs[t]]; labelT(t,e); labelS(bl[m],pi(bs[t],m)); } } bool bad=false; ll sum=0; rep(i,n)if(i> Q; assert(1 <= Q && Q <= 100); vectorL(Q), R(Q); for(int i = 0; i < Q; i++){ cin >> L[i] >> R[i]; assert(1 <= L[i] && L[i] < R[i] && R[i] <= 2*Q); L[i] -= 1; R[i] -= 1; } vectorA(2*Q); for(int i = 1; i < 2*Q; i++){ cin >> A[i]; assert(1 <= A[i] && A[i] <= 1e9); A[i] += A[i - 1]; } vector w(Q, vector(Q, none)); long long ret = 0; for(int i = 0; i < Q; i++){ ret += A[R[i]] - A[L[i]]; for(int j = 0; j < Q; j++){ if(i == j)continue; assert(L[i] != L[j]); assert(L[i] != R[j]); assert(R[i] != R[j]); assert(R[i] != L[j]); if(L[i] < L[j] && L[j] < R[i] && R[i] < R[j]){ w[i][j] = w[j][i] = A[R[i]] - A[L[j]]; } } } maxweight match(w); cout << ret - *max_element(match.ans.begin(), match.ans.end()) << endl; }