Mountain Climbing

• 기준이 좀 복잡한 그리디. 무지성 exchange argument로는 해결이 잘 안된다.
• 그리디 느낌은 오지만 한눈에 보이는 전략은 없으니 우선 무지성으로 exchange argument를 적용해보자. (a_up, a_down), (b_up, b_down)의 두 소가 있을때, a를 먼저 이동시키면 a_up + max(a_down, b_up) + b_down 이 걸리고, b를 먼저 이동시키면 b_up + max(b_down, a_up) + a_down 이 걸리므로, 저것을 비교함수로 해서 정렬하면 될것 같다는 느낌은 받을수 있다.
• 하지만, 식에 max도 섞여있고 정리가 잘 안된다. 그래서 저 관계가 진짜로 strict weak ordering을 만족하는지에 대한 확신이 잘 안생긴다. proof by AC로 증명하려고 시도했다가 실패하고 알아낸 반례는 (5,4), (3,3), (4,5) 이다. (4,5)와 (3,3), (3,3)과 (5,4)는 둘다 서로 순서를 바꿔도 전체 걸리는 시간이 똑같은 동등 관계이지만, (4,5)와 (5,4)는 (4,5)를 먼저 보내야만 더 시간이 적게 걸린다.
• 이런 경우를 해결하기 위해서, 둘다 동등관계이면 down - up 값이 더 작은 순서가 되도록 정렬기준을 바꿨다. 이제 (4,5)<(3,3)<(5,4) 가 되므로 이전 반례가 해결되고, 모든 경우에 대해서도 문제가 없는 것은 proof by AC로 증명된다;
• 이렇게 ac를 받기는 했지만.. 찜찜하다보니 b_down과 a_up의 대소관계와 a_down과 b_up의 대소관계에 따라서 경우를 4가지로 나누어서 생각함으로써 식을 정리해보려 했다. a를 먼저 보내는 조건이 min(a_up, b_down) < min(b_up, a_down) 으로 간단해지기는 했는데, 여기에서 더 진전은 없었다.
• 무지성으로 식을 먼저 세우고 그걸 정리하기보다는, 논리적으로 식을 도출해보자. 어떤 순서로 보내든 Farmer John은 쉬는 시간이 없다. 그러면 Farmer Don이 쉬는 시간을 최소화시키는 순서가 최적 순서인데, 그러려면 d>u 인것들을 먼저 다 보내고, 그 뒤에 d<u 인것들을 보내는 것이 최적이다. 이렇게 두 그룹으로 나눠서 각각에 대해서 따져보면, d>u 인 소들은 u가 작은것부터 보내는것이 최적이고, d<u인 소들은 d가 큰것부터 보내는 것이 최적이 된다.
• 이 전략을 그대로 구현하면, 두 그룹으로 나누고 각각을 소팅하게 된다. 그리고 잘 정리해보면 위에서 정렬한 방식과 동일한 결과가 된다는 것을 알수있다.
• 시간복잡도는 O(nlogn)

"""Solution code for "BOJ 5910. Mountain Climbing".

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

Tags: [greedy]
"""

import sys
import functools


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

    U_and_D.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
            )
        )
    )

    up_time = down_time = 0
    for u, d in U_and_D:
        up_time += u
        down_time = max(down_time, up_time) + d

    print(down_time)


if __name__ == '__main__':
    main()