题目描述

某训练集群需要依次完成 $n$ 个模型任务。对于每个任务，系统预先提供了两组可选的运行配置，不同配置会占用不同数量的计算资源，同时对应不同的训练耗时。

对于第 $i$ 个任务：

• 配置 1 需要消耗 $c_1$ 单位资源，训练耗时为 $t_1$；
• 配置 2 需要消耗 $c_2$ 单位资源，训练耗时为 $t_2$。

集群当前最多能够提供 $C$ 单位计算资源，其中资源统一按照“CPU 核心数 + GPU 显存 GB”计量。

现在需要为每个训练任务确定一种运行配置。每个任务必须且只能从两种配置中选择一种，所有任务所选择配置的资源消耗总和不能超过 $C$。

在满足资源限制的所有配置组合中，找到能够使所有任务总训练耗时最小的方案。

除了最小总训练耗时外，还需要统计该方案实际使用的资源总量，以及最终未被使用的剩余资源。

输入描述

第一行包含两个整数 $n$ 和 $C$，分别表示训练任务数量和集群能够提供的总算力资源上限。

其中：

$1\le n\le100，1\le C\le1000$

接下来共 $n$ 行，每行包含四个正整数 $c_1、t_1、c_2、t_2$。

对于第 $i$ 个任务：

• $c_1$ 表示选择方案1时的资源消耗；
• $t_1$ 表示选择方案1时的训练耗时；
• $c_2$ 表示选择方案2时的资源消耗；
• $t_2$ 表示选择方案2时的训练耗时。

数据满足：

$1\le c_1、c_2\le100，1\le t_1、t_2\le100$

输出描述

输出三个整数，整数之间使用一个空格分隔。

三个整数依次表示：

1. 在资源消耗不超过 $C$ 的条件下，可以得到的最小总训练耗时；
2. 对应方案实际消耗的总资源；
3. 资源分配完成后的剩余资源量。

其中：

剩余资源 = 上限$C$ - 实际消耗

样例1

输入：

2 15
5 6 8 3
7 5 9 2

输出：

8 14 1

样例说明

共有两个训练任务。

任务1选择方案1，需要 5 单位资源，耗时为 6；任务2选择方案2，需要 9 单位资源，耗时为 2。

此时资源总消耗为：

$5+9=14$

没有超过资源上限 $C=15$。

两个任务的总训练耗时为：

$6+2=8$

该结果是所有满足资源限制的选择方案中能够取得的最小总耗时。

因此实际使用资源为 14，剩余资源为 1，最终输出：

8 14 1

样例2

输入：

3 20
5 4 8 2
6 3 7 2
4 5 5 3

输出：

7 20 0

样例说明

三个任务均选择方案2时：

• 任务1消耗 8 单位资源，耗时为 2；
• 任务2消耗 7 单位资源，耗时为 2；
• 任务3消耗 5 单位资源，耗时为 3。

因此总资源消耗为：

$8+7+5=20$

恰好达到资源上限 $C=20$。

对应的总训练耗时为：

$2+2+3=7$

因此最小总训练耗时为 7，实际资源消耗为 20，没有剩余资源，输出：

7 20 0

例如，如果任务2改为选择方案1，则总资源消耗变为：

$8+6+5=19\le20$

对应总训练耗时为：

$2+3+3=8$

虽然该组合仍然满足资源限制，但总训练耗时大于 7，因此不是最优方案。