#include #include #include #include #include using namespace std; int n; vector> item; vector sum; long long dp[100001]; long long dfs(int id){ if(id == n){ return 0; } if(~dp[id]) return dp[id]; long long res = 1ll << 62, minItem = 1ll << 62; for(int i = id + 1; i <= n; i++){ if(id - i > 1 && item[i - 1].second > item[i - 1].first * 2) break; if(id - i > 1 && minItem > item[i - 1].first) break; minItem = min(minItem, item[i - 1].first); res = min(res, sum[i] - sum[id] - item[id].second + minItem + dfs(i)); } return dp[id] = res; } int main(){ cin >> n; item.resize(n); sum.resize(n + 1); for(auto&& i : item){ cin >> i.first >> i.second; } for(int i = 1; i <= n; i++){ sum[i] = sum[i - 1] + item[i - 1].first + item[i - 1].second; } memset(dp, -1, sizeof dp); cout << dfs(0) << "\n"; }