407878: GYM102916 B Fakes and Shidget

Memory Limit:512 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Fakes and Shidgettime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Pavel loves the game Fakes and Shidget very much. The game literally consists of the following process. The player uniformly randomly meets one of $$$n$$$ characters. Every character offers the player to choose one of two quests. The first quest of the $$$i$$$-th character requires $$$a_i$$$ minutes to complete and brings $$$b_i$$$ gold, and the second quest requires $$$c_i$$$ minutes and brings $$$d_i$$$ gold. The player chooses one of these quests, completes it and immediately meets another random character, and so on.

Pavel will play this game infinitely long. How fast can he earn gold if he will play optimally?

More formally, let $$$t$$$ is the time Pavel plays this game, and $$$g(t)$$$ is the amount of gold he earns for the time $$$t$$$. You should find the limit $$$\lim \limits_{t \to \infty} \frac{g\left(t\right)}{t}$$$.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 200000$$$) — the number of characters in the game.

Each of the next $$$n$$$ lines contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ and $$$d_i$$$ ($$$1 \le a_i, b_i, c_i, d_i \le 10^{9}$$$) — the duration of the first quest, the reward for the first quest, the duration of the second quest, the reward for the second quest of the $$$i$$$-th character.

Output

Output one floating-point number — the maximal possible speed of earning gold.

The absolute or relative error of the answer shouldn't exceed $$$10^{-9}$$$.

ExamplesInput
2
1 10 10 70
1 1 10 20
Output
6.454545454545455
Input
2
1 20 100 100
2 1 2 1
Output
7.000000000000000

加入题单

上一题 下一题 算法标签: