// #pragma GCC optimize ("O3") // #pragma GCC target("avx512f") // #pragma GCC optimize("unroll-loops") #ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include #include using namespace std; using namespace atcoder; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/ #define pb push_back #define pf push_front #define fi first #define se second #define eb emplace_back #define endl '\n' #define SZ(x) ((ll)(x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define debug(v) cout<<#v<<":";for(auto x:v){cout< Point; // Point typedef long long ll; typedef vector vl; typedef vectorvvl; typedef vectorvvvl; typedef vectorvvvvl; typedef vectorvvvvvl; typedef pair P; typedef tuple T; template using minpq=priority_queue,greater>; const ll MOD=1000000007LL; // const ll MOD=998244353LL; // using mint=modint998244353; // using mint=modint1000000007; using mint=modint; const ll mod=MOD; string abc="abcdefghijklmnopqrstuvwxyz"; string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; vl dx={0,0,1,-1,1,1,-1,-1}; vl dy={1,-1,0,0,-1,1,-1,1}; template vector make_vec(size_t a) { return vector(a); } template auto make_vec(size_t a, Ts... ts) { return vector(ts...))>(a, make_vec(ts...)); } templatebool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(bvm; typedef vectorvvm; typedef vectorvvvm; ll modpow(ll a, ll n,ll mod=MOD) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } /* UnionFind:素集合系管理の構造体(union by rank) isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n)) unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n)) */ struct UnionFind { // The range of node number is u 0 v n-1 vector rank, parents; UnionFind() {} UnionFind(int n) { // make n trees. rank.resize(n, 0); parents.resize(n, 0); for (int i = 0; i < n; i++) { makeTree(i); } } void makeTree(int x) { parents[x] = x; // the parent of x is x rank[x] = 0; } bool isSame(int x, int y) { return findRoot(x) == findRoot(y); } void unite(int x, int y) { x = findRoot(x); y = findRoot(y); if (rank[x] > rank[y]) { parents[y] = x; } else { parents[x] = y; if (rank[x] == rank[y]) { rank[y]++; } } } int findRoot(int x) { if (x != parents[x]) parents[x] = findRoot(parents[x]); return parents[x]; } }; // 辺の定義 struct Edge { long long u; long long v; long long cost; }; bool comp_e(const Edge &e1, const Edge &e2) { return e1.cost < e2.cost; } // 辺を直接比較するための関数 /* Kruskal :クラスカル法で minimum spanning tree を求める構造体 入力: 辺のvector, 頂点数V 最小全域木の重みの総和: sum 計算量: O(|E|log|V|) */ struct Kruskal { UnionFind uft; long long sum; // 最小全域木の重みの総和 vector edges; int V; Kruskal(const vector &edges_, int V_) : edges(edges_), V(V_) { init(); } void init() { sort(edges.begin(), edges.end(), comp_e); // 辺の重みでソート uft = UnionFind(V); sum = 0; for (auto e : edges) { if (!uft.isSame(e.u, e.v)) { // 閉路にならなければ加える uft.unite(e.u, e.v); sum += e.cost; } } } }; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(12); /*--------------------------------*/ int n;cin>>n; int V=n+1; vector edges; ll sum=0; for (int i = 0; i < n; i++) { ll c,d;cin>>c>>d; sum+=c; edges.pb({i,n,c}); if(i!=0)edges.pb({i-1,i,d}); } Kruskal krs(edges, V); cout << krs.sum+sum << endl; return 0; }