题目内容

某 $LLM$ 预训练团队从 $N$ 个数据源收集语料，每个数据源 $i$ 具有以下属性：

• $w_i$：占总训练 token 的权重比例，满足 $\sum_{i=1}^{N} w_i = 1$
• $r_i$：初始脏数据比例，0 < $r_i$ < 1
• $c_i$：基础清洗单价（正整数）

对每个数据源，可独立选择以下四种清洗级别之一：

整体语料的加权污染率定义为：

$R = \sum_{i=1}^{N} w_i \times r_i'$

在总花费不超过预算 $B$ 的前提下，为每个数据源选择一个清洗级别，使得加权污染率 $R$ 最小。

请实现指定函数接口，返回可达到的最小加权污染率，结果保留 $6$ 位小数。

输入描述

第 $1$ 行：

N B T

含义如下：

• $N$：数据源数量
• $B$：总预算上限
• $T$：总算力上限

接下来第 $N$ 行：

w_i r_i c_i t_i

含义如下：

• $w_i$：第 $i$ 个数据源的 $token$ 权重比例，所有 w_i 之和为 1
• $r_i$：第 $i$个数据源的初始脏数据比例
• $c_i$：第 $i$个数据源的基础清洗单价
• $t_i$：第 $i$ 个数据源的基础清洗算力消耗

输出描述

输出一个字符串，表示在预算 $B$ 和算力 $T$ 限制下可达到的最小加权污染率。结果保留 $6$ 位小数，不包含多余空格或换行。

样例1

输入

3 10 7
0.4 0.5 2 2
0.3 0.7 3 3
0.3 0.4 1 1

输出

0.270000

说明

• 源 $1$ 选 $2$ 级 + 源 $2$ 选 $1$ 级：花费 $6 + 3 = 9$，算力 $4 + 3 = 7$，源 $3$ 不清洗 $R = 0.040 + 0.126 + 0.120 = 0.286$

• 源 $1$ 选 $2$ 级 + 源 $3$ 选 $2$ 级：花费 $6 + 3 = 9$，算力 $4 + 2 = 6$，源 $2$ 不清洗 $R = 0.040 + 0.210 + 0.024 = 0.274$

• 源 $1$ 选 $1$ 级 + 源 $2$ 选 $1$ 级 + 源 $3$ 选 $2$ 级：花费 $2 + 3 + 3 = 8$，算力 $2 + 3 + 2 = 7$ $R = 0.120 + 0.126 + 0.024 = 0.270$

最小为 $0.270000$。

样例2

输入

2 6 4
0.5 0.8 2 2
0.5 0.6 3 1

输出

0.380000

说明

最小为方案“源 $1$ 选 $2$ 级”，$R = 0.380000$