P15124 [ICPC 2024 LAC] Joys of Trading

Apolyanka 和 Büdelsdorf 是两个最近才开始接触的新石器时代小村庄。有 $N$ 种资源，编号从 1 到 $N$，每个村庄都能独立生产其中任何一种，但效率不同。为了生产一单位资源 $i$，Apolyanka 需要 $A_i$ 人时，而 Büdelsdorf 需要 $B_i$ 人时。目前，在每个给定的时间段内，Apolyanka 生产 $U_i$ 单位资源 $i$，而 Büdelsdorf 生产 $W_i$ 单位。 每个村庄目前都在以最大产能工作，也就是说，他们无法投入比现在更多的人时。然而，通过最近发现的贸易优势，两个村庄有可能在减少总人时工作量的同时，生产出他们所需的所有资源，从而能够将这些节省下来的人时用于休息和玩一些游戏。所需要的就是村庄之间合作、协调并交换资源。 例如，假设 $N = 2$，资源 1 是木材，资源 2 是食物，$A_1 = 1$，$U_1 = 2$，$B_1 = 4$，$W_1 = 1$，$A_2 = 2$，$U_2 = 1$，$B_2 = 3$，$W_2 = 4$。那么 Apolyanka 正在做 4 人时的工作：生产 $U_1 = 2$ 单位木材需要 $A_1 \cdot U_1 = 2$，生产 $U_2 = 1$ 单位食物需要 $A_2 \cdot U_2 = 2$。类似地，Büdelsdorf 正在做 16 人时的工作：生产 $W_1 = 1$ 单位木材需要 $B_1 \cdot W_1 = 4$，生产 $W_2 = 4$ 单位食物需要 $B_2 \cdot W_2 = 12$。因此，总产量为 $U_1 + W_1 = 3$ 单位木材和 $U_2 + W_2 = 5$ 单位食物，需要 $4 + 16 = 20$ 人时。 然而，可以有一种更好的组织方式：Apolyanka 可以生产 3 单位木材和 0.5 单位食物，而 Büdelsdorf 可以不生产木材，生产 4.5 单位食物。每种资源的总产量将相同，但仅需要 $3A_1 + 0.5A_2 + 0B_1 + 4.5B_2 = 3 + 1 + 13.5 = 17.5$ 人时。 另一个 $N = 3$ 的例子是 $A_1 = 1$，$B_1 = 2$，$A_2 = 2$，$B_2 = 1$，$A_3 = 1$，$B_3 = 1$，且对于 $i = 1, 2, 3$，$U_i = W_i = 1$。在这种情况下，每个村庄目前都在工作 4 人时。然而，通过稍微调整，他们可以在生产完全相同的总资源的同时，每个只工作 3 人时！只需要 Apolyanka 少生产一单位资源 2，多生产一单位资源 1，而 Büdelsdorf 则相反。 给定所有这些值，你能计算出村庄为了生产完全相同总资源而必须工作的最小总人时数吗？请注意，生产一种资源所投入的人时数不必是整数。

第一行包含一个整数 $N$（$1 \le N \le 10^5$），表示资源的数量。每种资源由 $1$ 到 $N$ 之间的一个不同整数标识。 接下来的 $N$ 行中的第 $i$ 行描述资源 $i$，包含四个整数 $A_i$、$U_i$、$B_i$ 和 $W_i$（对于 $i = 1, 2, \dots, N$，有 $1 \le A_i, U_i, B_i, W_i \le 1000$），如题目描述中所述。

输出一行，表示生产这些资源所需的最小总人时数。输出的绝对误差或相对误差不得超过 $10^{-9}$。

翻译由 DeepSeek V3 完成