#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)n; i++) #define repf(i, a, b) for (ll i = (ll)a; i < (ll)b; i++) #define repr(i, a, b) for (ll i = (ll)a; i > (ll)b; i--) #define all(v) (v).begin(), (v).end() #define mp(a, b) make_pair(a, b) #define pb(x) push_back(x) #define eb(x) emplace_back(x) #define F first #define S second typedef long long ll; typedef long double ld; typedef pair pii; typedef pair pll; typedef pair pdd; typedef vector vll; typedef vector vvll; typedef vector vii; typedef vector vvii; const ll mod = 1e9 + 7; const int infi = 1147483600; const ll infl = 1e17; const char ENDL = '\n'; struct UnionFind { vector root; int n; void __init__(int sz) { n = sz; root.resize(n, -1); } int find(int x) { if (root[x] >= 0) { root[x] = find(root[x]); return root[x]; } return x; } bool unit(int a, int b) { int ra, rb; ra = find(a); rb = find(b); if (ra == rb) { return false; } else if (root[ra] <= root[rb]) { root[ra] += root[rb]; root[rb] = ra; } else { root[rb] += root[ra]; root[ra] = rb; } return true; } int count() { set cnt; rep(i, n) cnt.insert(find(i)); return cnt.size(); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin >> n; vector> edges; ll ans = 0; rep(i,n){ ll c, d; cin >> c >> d; ans += c; if (i>0)edges.eb(mp(d, mp(i - 1, i))); edges.eb(mp(c, mp(i, n))); } sort(all(edges)); UnionFind uf; uf.__init__(n + 1); for (auto p:edges){ ll d = p.F; ll x = p.S.F, y = p.S.S; if (uf.unit(x,y)){ ans += d; } } cout << ans << ENDL; }