| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 29 | 21 | 21 | 75.000% |
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 is capable of independently producing any of them, albeit with different efficiencies. In order to produce one unit of resource $i,ドル Apolyanka needs $A_i$ person-hours, while Büdelsdorf needs $B_i$ person-hours. Currently Apolyanka is producing $U_i$ units of resource $i$ in each given time period, while Büdelsdorf is producing $W_i$ units.
Each village is currently working at maximum capacity, that is, there is no way they can put more person-hours to work than they are employing now. However, through the recently discovered benefits of trade, it is possible for both villages to produce all the resources they need while reducing the total person-hours worked, and thus becoming able to spend those freed person-hours resting and playing some games. All that is needed is that the villages cooperate, coordinate work and exchange resources among them.
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$. Then Apolyanka is doing 4ドル$ person-hours of work: $A_1 \cdot U_1 = 2$ for producing $U_1 = 2$ units of wood, and $A_2 \cdot U_2 = 2$ for producing $U_2 = 1$ unit of food. Similarly, Büdelsdorf is doing 16ドル$ person-hours of work: $B_1 \cdot W_1 = 4$ for producing $W_1 = 1$ unit of wood, and $B_2 \cdot W_2 = 12$ for producing $W_2 = 4$ units of food. Thus, the total production is $U_1 + W_1 = 3$ units of wood and $U_2 + W_2 = 5$ units of food, requiring 4ドル + 16 = 20$ person-hours.
However, a better organization is possible: Apolyanka could produce 3ドル$ units of wood and 0ドル.5$ units of food, while Büdelsdorf could produce no wood and 4ドル.5$ units of food. The total production of each resource would be the same, but requiring only 3ドルA_1+0.5A_2+0B_1+4.5B_2 = 3 + 1 + 13.5 = 17.5$ person-hours.
Another example with $N = 3$ is $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$. In this case, each village is currently working 4ドル$ person-hours. With a slight reorganization however, they can each work 3ドル$ person-hours while producing the exact same total resources! All that is required is for Apolyanka to produce one less unit of resource 2ドル$ and one more of resource 1ドル,ドル while Büdelsdorf does the opposite.
Given all of these values, can you compute what is the minimum total number of person-hours that the villages have to work, in order to produce exactly the same total resources? Note that the number of person-hours invested in producing a resource is not required to be integer.
The first line contains an integer $N$ (1ドル ≤ N ≤ 10^5$) indicating the number of resources. Each resource is identified by a distinct integer from 1ドル$ to $N$.
The $i$-th of the next $N$ lines describes resource $i$ with four integers $A_i,ドル $U_i,ドル $B_i$ and $W_i$ (1ドル ≤ A_i , U_i , B_i , W_i ≤ 1000$ for $i = 1, 2, \dots , N$), as explained in the statement.
Output a single line with the minimum total number of person-hours required to produce the resources. The output must have an absolute or relative error of at most 10ドル^{-9 }$.
2 1 2 4 1 2 1 3 4
17.5
3 1 1 2 1 2 1 1 1 1 1 1 1
6