Gears and Axles

시간 제한1초메모리 제한1024 MB

요약
이 크기별로 묶인 기어들을 축에 물려 회전 속도를 최대한 높이고, 마지막 기어의 회전 속도에 자연로그를 취해 출력한다.
난이도

보통10점 중 6점

유형
그리디, 그래프, 수학, 정렬
정답자
아직 제출이 없습니다

문제

You have an assortment of circular gears with varying numbers and sizes of teeth. You also have a motor that spins at one revolution per second, as well as an unlimited number of (identical, arbitrarily long) axles. The motor and all gears fit the axles, and everything attached to a particular axle rotates at the same angular speed. Two gears with the same size teeth can be enmeshed with each other. Gears with different size teeth cannot be enmeshed with each other (though they can be placed on the same axle).

You can arrange the gears and axles in any order. What is the maximum rate at which the last gear/axle in sequence spins that you can achieve? Because this may be large, output the natural log of the value.

입력

The first line of input contains a single integer nn (0≤n≤1050≤n≤10^5) denoting the number of gears.

Each of the next nn lines contains two integers ss (1≤s≤1051≤s≤10^5) and cc (3≤c≤1053≤c≤10^5), one for each gear in your collection, where ss is the size of the teeth of the gear and cc is the count of the number of teeth.

출력

Output a single line with a single number equal to the natural log of the maximum angular speed you can achieve with your motor and axles and gears in your collection. This output will be considered correct if it is within an absolute or relative error of 10−610^{-6} .

예제2

  1. 예제 1

    입력
    6
    19 364
    21 1023
    19 66
    19 242
    21 807
    19 675
    
    예상 출력
    2.9704451880078357
    
  2. 예제 2

    입력
    4
    33 10
    33 27
    44 10
    44 27
    
    예상 출력
    1.9865035460205664