问题陈述
我们种下了$N$花种子,所有这些种子都会开出不同的花。 我们想让所有的花朵一起绽放。
每种植物都有一个称为生命力的值,该值最初为零。 浇水和施肥会导致其发生变化,如果第 $i$ 棵植物的生命力等于或大于 $\mathit{th}_i$,它就会开花。 请注意,$\mathit{th}_i$ 可能为负数,因为有些花不需要额外的营养。
浇水对所有植物的影响。 用 $W$ 升水浇灌植物,对于所有 $i$ ($1 \le i \le n$),第 $i$ 个植物的生命力会改变 $W \times \mathit{vw}_i$ ,并花费 $W \times \mathit{pw}$ 日元,其中 $W$ 不必是整数。 $\mathit{vw}_i$ 可能为负,因为有些花讨厌水。
我们有 $N$ 种肥料,第 $i$ 种肥料仅对第 $i$ 种植物有效。 撒播 $F_i$ 公斤的第 $i$ 肥料将第 $i$ 个植物的生命力改变 $F_i \times \mathit{vf}_i$,并花费 $F_i \times \mathit{pf}_i$ 日元,其中 $F_i$ 也不必是整数。 每种肥料都是专门为相应的植物制作的,因此 $\mathit{vf}_i$ 保证为正数。
当然,我们也希望成本最小化。 正式地,我们的目的被描述为“在 $W \times \mathit{vw}_i + F_i \times \mathit{vf}_i \ge \mathit{th}_i$、$W \ge 0$ 和 $F_i \ge 下最小化 $W \times \mathit{pw} + \sum_{i=1}^{N}(F_i \times \mathit{pf}_i)$ 0$ 对于所有 $i$ ($1 \le i \le N$)"。 您的任务是计算最低成本。
输入
输入由多个数据集组成。 数据集数量不超过$100$,输入数据大小不超过$20\mathrm{MB}$。 每个数据集的格式如下。
$N$
$\mathit{pw}$
$\mathit{vw}_1$ $\mathit{pf}_1$ $\mathit{vf}_1$ $\mathit{th}_1$
:
:
$\mathit{vw}_N$ $\mathit{pf}_N$ $\mathit{vf}_N$ $\mathit{th}_N$
数据集的第一行包含一个整数 $N$,即花种子的数量。 数据集的第二行包含一个整数 $\mathit{pw}$,即浇水一升的成本。 以下每行 $N$ 描述一朵花。第 $i$ 行包含四个整数:$\mathit{vw}_i$、$\mathit{pf}_i$、$\mathit{vf}_i$ 和 $\mathit{th}_i$,用空格分隔。
您可以假设 $1 \le N \le 10^5$、$1 \le \mathit{pw} \le 100$、$-100 \le \mathit{vw}_i \le 100$、$1 \le \mathit{pf}_i \le 100$、$1 \le \mathit{vf}_i \le 100$ 和 $-100 \le \mathit{th}_i \le 100$。
输入的结尾由包含零的行指示。
输出
对于每个数据集,输出一行包含使所有花朵绽放的最小成本。 输出的绝对或相对误差不得超过 $10^{-4}$。
示例输入
3 10 4 3 4 10 5 4 5 20 6 5 6 30 3 7 -4 3 4 -10 5 4 5 20 6 5 6 30 3 1 -4 3 4 -10 -5 4 5 -20 6 5 6 30 3 10 -4 3 4 -10 -5 4 5 -20 -6 5 6 -30 0
样本输入的输出
43.5 36 13.5 0