#include #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" #define NDEBUG #define SHOW(...) static_cast(0) //!===========================================================!// //! dP dP dP !// //! 88 88 88 !// //! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !// //! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !// //! 88 88 88. ... 88. .88 88. .88 88. ... 88 !// //! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !// //!===========================================================!// template T read() { T v; return std::cin >> v, v; } template std::vector readVec(const std::size_t l) { std::vector v(l); for (auto& e : v) { std::cin >> e; } return v; } using ld = long double; using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr unsigned int MOD = 1000000007; template constexpr T INF = std::numeric_limits::max() / 4; template constexpr F PI = static_cast(3.1415926535897932385); std::mt19937 mt{std::random_device{}()}; template bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); } template bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); } template std::vector Vec(const std::size_t n, T v) { return std::vector(n, v); } template auto Vec(const std::size_t n, Args... args) { return std::vector(n, Vec(args...)); } template constexpr T popCount(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : (T)__builtin_popcountll(u); #else unsigned long long v = static_cast(u); return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); #endif } template constexpr T log2p1(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : T(64 - __builtin_clzll(u)); #else unsigned long long v = static_cast(u); return v = static_cast(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), popCount(v); #endif } template constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); } template constexpr T msbp1(const T v) { return log2p1(v); } template constexpr T lsbp1(const T v) { #ifdef __has_builtin return __builtin_ffsll(v); #else return v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1); #endif } template constexpr bool ispow2(const T v) { return popCount(v) == 1; } template constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); } //!===================================================================!// //! .d88888b d888888P !// //! 88. "' 88 !// //! 'Y88888b. .d8888b. .d8888b. 88 88d888b. .d8888b. .d8888b. !// //! '8b 88ooood8 88' '88 88 88' '88 88ooood8 88ooood8 !// //! d8' .8P 88. ... 88. .88 88 88 88. ... 88. ... !// //! Y88888P '88888P' '8888P88 dP dP '88888P' '88888P' !// //! .88 !// //! d8888P !// //!===================================================================!// template class SegTree { public: using ValType = typename ValMonoid::ValType; SegTree(const std::size_t N, const ValType initial = ValMonoid::id()) : size(N), half(ceil2(size)), val(half << 1, ValMonoid::id()) { if (initial != ValMonoid::id()) { std::fill(val.begin() + half, val.end(), initial); for (std::size_t i = half - 1; i >= 1; i--) { up(i); } } } template SegTree(const InIt first, const InIt last) : size(std::distance(first, last)), half(ceil2(size)), val(half << 1, ValMonoid::id()) { std::copy(first, last, val.begin() + half); for (std::size_t i = half - 1; i >= 1; i--) { up(i); } } ValType get(const std::size_t a) const { return assert(a < size), val[a + half]; } void set(std::size_t a, const ValType& v) { assert(a < size); val[a += half] = v; while (a >>= 1) { up(a); } } ValType fold(std::size_t L, std::size_t R) const { assert(L < R), assert(R <= size); ValType accl = ValMonoid::id(), accr = ValMonoid::id(); for (L += half, R += half; L < R; L >>= 1, R >>= 1) { if (L & 1) { accl = acc(accl, val[L++]); } if (R & 1) { accr = acc(val[--R], accr); } } return acc(accl, accr); } friend std::ostream& operator<<(std::ostream& os, const SegTree& seg) { os << "["; for (std::size_t i = seg.half; i < seg.half + seg.size; i++) { os << seg.val[i] << (i + 1 == seg.half + seg.size ? "" : ","); } return (os << "]\n"); } private: void up(const std::size_t i) { val[i] = acc(val[i << 1], val[i << 1 | 1]); } const std::size_t size, half; std::vector val; const ValMonoid acc{}; }; //!============================!// //! 8888ba.88ba oo !// //! 88 '8b '8b !// //! 88 88 88 dP 88d888b. !// //! 88 88 88 88 88' '88 !// //! 88 88 88 88 88 88 !// //! dP dP dP dP dP dP !// //!============================!// template struct Min { using ValType = Elemtype; ValType operator()(const ValType& a, const ValType& b) const { return std::min(a, b); } static constexpr ValType id() { return std::numeric_limits::max(); } }; //!=====================================!// //! 8888ba.88ba oo !// //! 88 '8b '8b !// //! 88 88 88 .d8888b. dP 88d888b. !// //! 88 88 88 88' '88 88 88' '88 !// //! 88 88 88 88. .88 88 88 88 !// //! dP dP dP '88888P8 dP dP dP !// //!=====================================!// int main() { const int N = read(); std::vector C(N), D(N); ll ans = 0; for (int i = 0; i < N; i++) { std::cin >> C[i] >> D[i], ans += C[i] + D[i]; } auto dp = Vec(N, 3, INF); dp[0][0] = 0; for (int i = 0; i < N; i++) { chmin(dp[i][1], dp[i][0] - D[i]); chmin(dp[i][2], dp[i][1] + C[i]); if (i < N - 1) { chmin(dp[i + 1][0], dp[i][2]); chmin(dp[i + 1][1], dp[i][1]); chmin(dp[i + 1][2], dp[i][2]); } } std::cout << ans + dp[N - 1][2] << std::endl; return 0; }