← 返回题目列表

AtCoder · icpc2014autumn_d

D. 鲜花

中文机器翻译题面 查看原题

问题陈述

我们种下了$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