여분의 저장 공간

여러 종류의 파일 시스템을 쓰는 하드 드라이브로 이루어진 대규모 컴퓨터 클러스터를 관리한다. 최근에 모든 드라이브의 파일 시스템을 한 종류로 통일하기로 정했다. 쉬운 일이 아니다. 드라이브는 전부 사용 중이고, 하나도 빠짐없이 용량 한계까지 중요한 데이터로 채워져 있으며, 데이터는 1기가바이트도 잃을 수 없다. 게다가 새 파일 시스템으로 다시 포맷하면 그 드라이브의 용량이 크게 달라질 수 있다. 포맷을 시작할 수 있게 만들려면 여분의 하드 드라이브를 사야 한다. 물론 이 여분 저장 공간의 크기를 최소로 줄여서 돈을 아끼고 싶다.

드라이브는 어떤 순서로든 포맷할 수 있다. 어떤 드라이브를 포맷하기 전에는 그 드라이브의 데이터를 전부 다른 드라이브로 옮겨야 하고, 필요하면 여러 드라이브에 나눠 담아도 된다. 포맷이 끝난 드라이브는 곧바로 다른 드라이브의 데이터를 담는 데 쓸 수 있다. 데이터를 원래 있던 드라이브로 되돌릴 필요는 없다. 새 파일 시스템에서 용량이 줄어드는 드라이브가 있으면 되돌리는 것 자체가 불가능하기도 하다. 데이터 일부가 여분 드라이브에 남아 있어도 된다.

예를 들어 용량이 각각 6, 1, 3, 3기가바이트인 드라이브 A, B, C, D가 있고 새 파일 시스템에서 용량이 각각 6, 7, 5, 5기가바이트가 된다고 하자. 여분 공간을 1기가바이트만 사면 B의 데이터를 그곳으로 옮긴 뒤 B를 포맷할 수 있다. 이제 B가 7기가바이트 비어 있으니 A의 6기가바이트를 B로 옮기고 A를 포맷한다. 마지막으로 C와 D에 있는 6기가바이트를 A로 옮기고 C와 D를 포맷한다.

첫 줄에 클러스터에 있는 드라이브의 개수 $n$ ($1 \le n \le 10^6$)이 주어진다. 이어지는 $n$개의 줄에는 드라이브 하나를 설명하는 두 정수 $a$와 $b$가 주어진다. $a$는 예전 파일 시스템에서의 용량이고, $b$는 새 파일 시스템에서의 용량이다.

모든 용량은 기가바이트 단위이며 $1 \le a, b \le 10^9$을 만족한다. (1000페타바이트면 누구에게나 충분하지 않을까?)

모든 드라이브를 포맷하려면 여분 공간을 최소 몇 기가바이트 사야 하는지 한 줄에 출력한다.