소방서의 고민

울릉도의 한 소방서에는 소방차가 한 대뿐이다. 그런데 시각 0에 여러 건의 화재가 동시에 발생했다. 소방차는 한 번에 한 화재만 진압할 수 있고, 어떤 화재를 완전히 진압하기 전에는 다른 화재 현장으로 이동할 수 없다. 이동 시간은 0초로 본다.

각 화재는 늦게 도착할수록 진압 시간이 같거나 길어진다. 어떤 화재에 대해, 화재 발생 후 t초 뒤에 소방차가 도착하면 그 화재를 진압하는 데 걸리는 시간은 a t + b초이다. 여기서 a와 b는 음이 아닌 정수이며, 화재마다 값이 다를 수 있다.

모든 화재를 진압하는 순서를 적절히 정했을 때, 모든 화재를 진압하는 데 걸리는 최소 시간을 구하라.

첫째 줄에 화재 발생 건수 n이 주어진다. n은 200,000 이하의 양의 정수이다.

둘째 줄부터 n개의 줄에는 각 화재의 두 정수 a와 b가 한 줄에 하나씩 주어진다. a와 b는 각각 40,000 이하의 음이 아닌 정수이다.

모든 화재를 진압하는 데 걸리는 최소 시간을 40,000으로 나눈 나머지를 출력한다.