Joys of Trading

Apolyanka and Büdelsdorf are two small neolithic villages that have recently come into contact. There are $N$ resources, numbered from $1$ to $N$, and each village can independently produce any of them, though with different efficiencies. To produce one unit of resource $i$, Apolyanka needs $A_i$ person-hours, while Büdelsdorf needs $B_i$ person-hours. Currently Apolyanka produces $U_i$ units of resource $i$ in each time period, and Büdelsdorf produces $W_i$ units. Each village already works at maximum capacity, so neither can put more person-hours to work than it employs now. Through trade, however, both villages can still produce everything they need while reducing the total person-hours worked, which frees time for rest and games. All that is needed is for the villages to cooperate, coordinate their work, and exchange resources.

For example, suppose $N = 2$, resource 1 is wood, resource 2 is food, $A_1 = 1$, $U_1 = 2$, $B_1 = 4$, $W_1 = 1$, $A_2 = 2$, $U_2 = 1$, $B_2 = 3$, and $W_2 = 4$. Apolyanka works 4 person-hours: $A_1 U_1 = 2$ for 2 units of wood, and $A_2 U_2 = 2$ for 1 unit of food. Büdelsdorf works 16 person-hours: $B_1 W_1 = 4$ for 1 unit of wood, and $B_2 W_2 = 12$ for 4 units of food. The total output is 3 units of wood and 5 units of food, using 20 person-hours.

A better organization exists. Apolyanka produces 3 units of wood and 0.5 units of food, and Büdelsdorf produces no wood and 4.5 units of food. The totals stay the same, but the work drops to $3A_1 + 0.5A_2 + 0B_1 + 4.5B_2 = 3 + 1 + 13.5 = 17.5$ person-hours.

Another example with $N = 3$ has $A_1 = 1$, $B_1 = 2$, $A_2 = 2$, $B_2 = 1$, $A_3 = 1$, $B_3 = 1$, and $U_i = W_i = 1$ for $i = 1, 2, 3$. Each village works 4 person-hours. With a small reorganization, each can work 3 person-hours while producing the same total resources. Apolyanka makes one less unit of resource 2 and one more unit of resource 1, and Büdelsdorf does the opposite.

Given these values, compute the minimum total number of person-hours the villages must work to produce exactly the same total resources. The person-hours spent on a resource need not be an integer.

The first line contains an integer $N$ ($1 \le N \le 10^5$), the number of resources. Each resource is identified by a distinct integer from $1$ to $N$. The $i$-th of the next $N$ lines contains four integers $A_i$, $U_i$, $B_i$, and $W_i$ ($1 \le A_i, U_i, B_i, W_i \le 1000$ for $i = 1, 2, \dots, N$), as described in the statement.

Output a single line with the minimum total number of person-hours required to produce the resources. The answer must have an absolute or relative error of at most $10^{-9}$.