//#pragma GCC optimize ("-O3","unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define REVERSE(v,n) reverse(v,v+n); #define VREVERSE(v) reverse(v.begin(), v.end()); #define ll long long #define pb(a) push_back(a) #define m0(x) memset(x,0,sizeof(x)) #define print(x) cout< inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } const int MOD = 1e9 + 7; const ll INF = 1e17; const double pi = acos(-1); const double EPS = 1e-10; typedef pairP; const int MAX = 200020; const int MAX_N = 1 << 17; int n; int dat[2 * MAX_N - 1];//セグ木を持つグローバル配列 //初期化 void init(int n_) { n = 1; //簡単のため、要素数を2のべき乗に while (n < n_)n *= 2; //gcdに影響を与えない値で初期化する for (int i = 0; i < 2 * n - 1; i++)dat[i] = INF; } //k番目の値(0-indexed)をaに更新 void update(int k, int a) { k += n - 1;//葉の節点 dat[k] = a; //上りながら更新 while (k > 0) { k = (k - 1) / 2; dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); } } //[a,b)のgcdを求める //そとからは、(a,b,0,0,n)として呼ぶ int query(int a, int b, int k, int l, int r) { //[a,b)と[l,r)が交差していなければ、gcdに影響を与えない値を返す //関数定義でgcdの単位元を0としている if (r <= a || b <= l)return INF; //[a,b)が[l,r)を完全に含んでいれば、この節点の値 if (a <= l && r <= b)return dat[k]; //そうでなければ、二つの子のgcd else { int vl = query(a, b, k * 2 + 1, l, (l + r) / 2); int vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } } int N; int C[100010], D[100010]; vectortop; signed main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; init(N); REP(i, N) { cin >> C[i] >> D[i]; update(i, C[i]); } top.pb(0); int l = 0; int ans = 0; FOR(i, 1, N) { int leftmin = query(l, i, 0, 0, n); if (D[i] + min(leftmin, C[i]) > leftmin + C[i]) { top.pb(i); l = i; } } top.pb(N); REP(i, top.size()-1) { //pe(top[i]); FOR(j, top[i], top[i + 1]) { ans += C[j] + D[j]; } ans -= D[top[i]]; ans += query(top[i], top[i + 1], 0, 0, n); }cout << endl; print(ans); }