Cakes

• Mountain Climbing 과 거의 동일한 문제. Mountain Climbing과 다른 점은, 두번째 작업을 진행하는 순서를 첫번쨰 작업을 진행한 순서와 다르게 해도 상관없다는 부분인데, 실제 풀이는 어차피 동일하다.
• 풀이는 Mountain Climbing을 참고. 덤으로, The Milk Queue도 동일한 문제.

"""Solution code for "BOJ 7744. Cakes".

- Problem link: https://www.acmicpc.net/problem/7744
- Solution link: http://www.teferi.net/ps/problems/boj/7744

Tags: [greedy]
"""

import sys
import functools


def main():
    N = int(sys.stdin.readline())
    a_and_b = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    a_and_b.sort(
        key=functools.cmp_to_key(
            lambda x, y: (
                (x[0] - x[1]) - (y[0] - y[1])
                if (comp := min(x[0], y[1]) - min(x[1], y[0])) == 0
                else comp
            )
        )
    )

    prepare_time = bake_time = 0
    for a, b in a_and_b:
        prepare_time += a
        bake_time = max(bake_time, prepare_time) + b

    print(bake_time)


if __name__ == '__main__':
    main()