//include //------------------------------------------ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";} #define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}} using LL = long long; //------------------------------------------ //------------------------------------------ struct UnionFind { vector par; vector sizes; UnionFind(int n) : par(n), sizes(n, 1) { for (int i = 0; i < n; i++) { par[i] = i; } } int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (sizes[x] < sizes[y]) swap(x, y); par[y] = x; sizes[x] += sizes[y]; } bool same(int x, int y) { return find(x) == find(y); } int get_size(int x) { return sizes[find(x)]; } bool all_same() { bool good = true; for (int i = 0, n = par.size(); i < n; i++) if (find(0) != find(i)) good = false; return good; } int get_connectivity() { set s; for (int i = 0, n = par.size(); i < n; i++) s.insert(find(i)); return s.size(); } }; int main() { int N; cin >> N; UnionFind UF(N + 1); vector C(N), D(N); for (int i = 0; i < N; i++) cin >> C[i] >> D[i]; vector> edges; for (int i = 0; i < N; i++) { edges.push_back(make_tuple(C[i], i, N)); } for (int i = 1; i < N; i++) { edges.push_back(make_tuple(D[i], i - 1, i)); } sort(edges.begin(), edges.end()); LL ans = accumulate(C.begin(), C.end(), 0LL); for (auto &e : edges) { LL cost, fm, to; tie(cost, fm, to) = e; if (!UF.same(fm, to)) { UF.unite(fm, to); ans += cost; } } cout << ans << endl; }