407878: GYM102916 B Fakes and Shidget

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}$$$.

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 one floating-point number — the maximal possible speed of earning gold.

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

2
1 10 10 70
1 1 10 20

6.454545454545455

2
1 20 100 100
2 1 2 1

7.000000000000000