문제
빅 데이터 연구실에 있는 한제 조교는 빅 데이터 시스템에 있는 여러개의 드라이브를 운영 관리하고 있다. ext3 파일 시스템으로 관리하고 있었는데, ZFS라는 새로운 파일 시스템을 교수님이 세미나에서 듣고 오시더니, 한제 조교가 관리하는 빅 데이터의 모든 꽉 찬 하드 드라이브 파일 시스템을 ZFS로 교체하라고 시키셨다. ext3 파일 시스템을 쓰고 있는 하드 드라이브 ZFS 파일 시스템으로 교체하면 각 드라이브에 저장할 수 있는 용량이 바뀐다. 파일 시스템을 바꾸려면 기존 하드에 있는 내용을 임시 드라이브나, ZFS 시스템으로 교체하여 생긴 여유 공간에 저장해서 내용을 전부 옮긴 후에 파일 시스템을 바꿔야 한다.
한제 조교는 ZFS로 파일 시스템을 교체하기 위해 용산에 하드를 사러 가는 길이다. 하드는 용량이 커질수록 가격이 비싸지니 최대한 용량이 작은 하드를 사용해서 연구실에 있는 드라이브의 파일 시스템을 바꿔보자.
입력
첫 번째 줄에는 한제 조교가 관리하는 총 하드 드라이브의 갯수 N(5≤N≤100,000)가 주어진다.
N+1 줄까지 두 개의 자연수가 주어지는데 첫 번째 숫자는 현재 꽉 찬 ext3 파일 시스템 용량이고, 두 번째 숫자는 해당 드라이브를 ZFS 파일 시스템으로 바꿨을때 저장할 수 있는 용량이 주어진다. 각 드라이브의 변경 전 용량과 변경 후 용량은 1,048,576을 넘지 않는다.
ZFS로 바꾼 후에 총 용량이 줄어들면 사온 하드에 데이터를 저장해야 한다.
출력
구매해야 하는 최소한의 임시 하드 용량을 출력한다.
예제
5
7 5
2 2
1 2
3 6
5 4
3
출처
ACM-ICPC World Finals 2016 문제 L번
로그인해야 코드를 작성할 수 있어요.