Score : 1100 points
We have N balance beams numbered 1 to N. The length of each beam is 1 meters. Snuke walks on Beam i at a speed of 1/A_i meters per second, and Ringo walks on Beam i at a speed of 1/B_i meters per second.
Snuke and Ringo will play the following game:
Find the probability that Snuke wins when Snuke arranges the N beams so that the probability of his winning is maximized.
This probability is a rational number, so we ask you to represent it as an irreducible fraction P/Q (to represent 0, use P=0, Q=1).
Input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Print the numerator and denominator of the irreducible fraction that represents the maximum probability of Snuke's winning.
2 3 2 1 2
1 4
When the beams are connected in the order 2,1 from left to right, the probability of Snuke's winning is 1/4, which is the maximum possible value.
4 1 5 4 7 2 1 8 4
1 2
3 4 1 5 2 6 3
0 1
10 866111664 178537096 705445072 318106937 472381277 579910117 353498483 865935868 383133839 231371336 378371075 681212831 304570952 16537461 955719384 267238505 844917655 218662351 550309930 62731178
697461712 2899550585