슈퍼컴퓨터

바이토리치(BajtoLicz)는 매우 빠른 서버 BL87을 보유하고 있다. 이 서버의 성능을 활용하기 위해, 회사는 고객이 보낸 프로그램을 서버에서 대신 실행해 주는 서비스를 시작하기로 했다. 보내진 각 프로그램은 실행을 위해 일정한 계산량(프로세서 시간)을 필요로 한다.

프로그램의 실행 시간은 회사가 그 프로그램을 받은 순간부터 실행이 끝나는 순간까지로 계산한다. 즉, 한 프로그램의 실행 시간은 (완료 시각) $-$ (도착 시각) 이다.

서버 BL87은 여러 프로그램을 동시에 병렬로 실행할 수 있으며, 실행 중인 각 프로그램은 (우선순위에 따라 정해지는) 프로세서 성능의 일정 비율을 배정받는다. 프로세서 전체 성능은 100%로 고정되어 있어, 어느 순간에든 실행 중인 프로그램들에 배분된 비율의 합은 100%를 넘을 수 없다. 서로 다른 우선순위에 따라 프로그램의 실행을 중단하고 다시 이어서 실행하는 것도 가능하다.

주어진 작업 목록에 대해, 모든 작업의 실행 시간의 합을 최소로 만드는 값을 구하는 프로그램을 작성하여라.

작성할 프로그램은 다음을 수행한다.

• 서버에서 실행해야 하는 프로그램의 개수와 각 프로그램의 정보를 입력받는다.
• 모든 작업의 실행 시간의 합의 최솟값을 구한다.
• 그 결과를 출력한다.

첫째 줄에는 실행할 프로그램의 개수를 나타내는 정수 $n$ ($1 \le n \le 100000$)이 주어진다. 다음 $n$개의 각 줄에는 두 정수 $a$와 $b$ ($0 \le a, b \le 10^9$)가 주어지며, 각각 그 프로그램이 도착한 시각과 그 프로그램의 실행에 필요한 프로세서 시간을 의미한다.

첫째 줄에 모든 프로그램의 실행 시간의 합의 최솟값을 나타내는 정수 $k$ 하나를 출력한다.