여러분은 데이터를 저장하는데 다양한 파일 시스템을 사용하는 하드 드라이브를 장착한 많은 컴퓨터를 관리합니다. 최근 여러분은 파일 시스템을 동일한 종류로 통일시키기로 결정했습니다. 현재 사용 중인 모든 드라이브는 현재 용량만큼 중요한 데이터로 가득 차 있으며, 이들 데이터가 손실되어서는 안 되기 때문에, 이러한 결정은 상당히 어려운 도전입니다. 게다가, 새로운 파일 시스템을 사용하기 위해 드라이브를 포맷하는 것은 드라이브의 용량을 크게 바꿀 수 있습니다. 포맷을 하기 위해 여러분은 하드 드라이브 하나를 새로 사야 할 것입니다. 확실한 것은 새로 구매할 드라이브의 용량을 최대한 작게 해서 돈을 아끼고 싶다는 것입니다.
여러분은 드라이브를 임의의 순서대로 포맷시킬 수 있습니다. 드라이브를 포맷하기 전에, 여러분은 포맷시킬 드라이브에 있는 데이터를 하나 이상의 드라이브(들)에 옮겨놓아야 합니다. 드라이브를 포맷한 후에는, 다른 드라이브의 데이터를 저장하기 위해 포맷한 드라이브를 즉시 사용할 수 있습니다. 모든 데이터를 처음에 담아뒀던 드라이브에 저장할 필요는 없습니다. 사실, 몇몇 드라이브들이 새로운 파일 시스템에서 용량이 더 작아지는 경우 그렇게 하는 것이 아예 불가능할 수도 있습니다! 또한, 여러분이 새로 구매한 드라이브에 일부 데이터를 담을 수도 있습니다.
예를 들어, 여러분이 드라이브 A, B, C, D를 갖고 있고 각각의 용량이 6GB, 1GB, 3GB, 3GB라고 합시다. 새 파일 시스템에서 각 드라이브의 용량은 각각 6GB, 7GB, 5GB, 5GB가 됩니다. 여러분이 단 1GB 용량의 드라이브를 구매함으로써, 드라이브 B의 데이터를 새로 구매한 드라이브에 옮긴 후 B를 포맷할 수 있습니다. 이제 여러분은 B에 7GB의 여유 용량을 확보했으며, A의 데이터 6GB를 B에 옮기고 A를 포맷할 수 있습니다. 마지막으로, C, D에서 총 6GB의 데이터를 A에 옮긴 후 C와 D를 포맷하면 됩니다.
--------
[입력]
입력의 첫 줄에는 여러분이 관리하는 컴퓨터의 드라이브 개수가 하나의 정수 n (1 ≤ n ≤ 106)으로 주어집니다. 다음 n개 줄에는, 한 줄에 두 정수 a, b가 입력됩니다. a는 기존 파일 시스템에서, b는 새 파일 시스템에서의 드라이브의 용량입니다. 모든 용량은 GB 단위로 주어지며, 1 ≤ a, b ≤ 109를 충족합니다. (1000PB 정도면 모두에게 충분한 용량이겠죠?)
--------
[출력]
여러분이 모든 드라이브를 포맷하기 위해 구매해야 할 드라이브의 용량을 GB 단위로 출력합니다.
moner_ari 1년 전 3
[문제]
여러분은 데이터를 저장하는데 다양한 파일 시스템을 사용하는 하드 드라이브를 장착한 많은 컴퓨터를 관리합니다. 최근 여러분은 파일 시스템을 동일한 종류로 통일시키기로 결정했습니다. 현재 사용 중인 모든 드라이브는 현재 용량만큼 중요한 데이터로 가득 차 있으며, 이들 데이터가 손실되어서는 안 되기 때문에, 이러한 결정은 상당히 어려운 도전입니다. 게다가, 새로운 파일 시스템을 사용하기 위해 드라이브를 포맷하는 것은 드라이브의 용량을 크게 바꿀 수 있습니다. 포맷을 하기 위해 여러분은 하드 드라이브 하나를 새로 사야 할 것입니다. 확실한 것은 새로 구매할 드라이브의 용량을 최대한 작게 해서 돈을 아끼고 싶다는 것입니다.
여러분은 드라이브를 임의의 순서대로 포맷시킬 수 있습니다. 드라이브를 포맷하기 전에, 여러분은 포맷시킬 드라이브에 있는 데이터를 하나 이상의 드라이브(들)에 옮겨놓아야 합니다. 드라이브를 포맷한 후에는, 다른 드라이브의 데이터를 저장하기 위해 포맷한 드라이브를 즉시 사용할 수 있습니다. 모든 데이터를 처음에 담아뒀던 드라이브에 저장할 필요는 없습니다. 사실, 몇몇 드라이브들이 새로운 파일 시스템에서 용량이 더 작아지는 경우 그렇게 하는 것이 아예 불가능할 수도 있습니다! 또한, 여러분이 새로 구매한 드라이브에 일부 데이터를 담을 수도 있습니다.
예를 들어, 여러분이 드라이브 A, B, C, D를 갖고 있고 각각의 용량이 6GB, 1GB, 3GB, 3GB라고 합시다. 새 파일 시스템에서 각 드라이브의 용량은 각각 6GB, 7GB, 5GB, 5GB가 됩니다. 여러분이 단 1GB 용량의 드라이브를 구매함으로써, 드라이브 B의 데이터를 새로 구매한 드라이브에 옮긴 후 B를 포맷할 수 있습니다. 이제 여러분은 B에 7GB의 여유 용량을 확보했으며, A의 데이터 6GB를 B에 옮기고 A를 포맷할 수 있습니다. 마지막으로, C, D에서 총 6GB의 데이터를 A에 옮긴 후 C와 D를 포맷하면 됩니다.
--------
[입력]
입력의 첫 줄에는 여러분이 관리하는 컴퓨터의 드라이브 개수가 하나의 정수 n (1 ≤ n ≤ 106)으로 주어집니다. 다음 n개 줄에는, 한 줄에 두 정수 a, b가 입력됩니다. a는 기존 파일 시스템에서, b는 새 파일 시스템에서의 드라이브의 용량입니다. 모든 용량은 GB 단위로 주어지며, 1 ≤ a, b ≤ 109를 충족합니다. (1000PB 정도면 모두에게 충분한 용량이겠죠?)
--------
[출력]
여러분이 모든 드라이브를 포맷하기 위해 구매해야 할 드라이브의 용량을 GB 단위로 출력합니다.