#include #include #include using namespace std; #define MAX 110000 int per[MAX], siz[MAX]; void init(int n){ for(int i = 0; i < n; i++){ per[i] = i; siz[i] = 1; } } int find(int x){ if(x == per[x]) return x; else return per[x] = find(per[x]); } void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(siz[x] > siz[y]){ siz[x] += siz[y]; per[y] = x; } else { siz[y] += siz[x]; per[x] = y; } } bool same(int x, int y){ return find(x) == find(y); } int kruskal(vector > > &edge){ int res = 0; sort(edge.begin(), edge.end()); for(int i = 0; i < edge.size(); i++){ if(same(edge[i].second.first, edge[i].second.second)) continue; unite(edge[i].second.first, edge[i].second.second); res += edge[i].first; } return res; } signed main(){ int N, sum = 0; int C, D; vector > > edge; cin>>N; for(int i = 1; i <= N; i++){ cin>>C>>D; sum += C; edge.push_back(make_pair(C ,make_pair(0,i))); if(i != 1) edge.push_back(make_pair(D ,make_pair(i-1,i))); } init(N+2); cout<