题目内容

一个模型训练集群需要依次执行 $n$ 个任务。对于任意第 $i$ 个任务，调度系统已经给出两套候选配置，它们在计算资源占用和训练耗时上各有差异。

具体地，若第 $i$ 个任务采用配置 1，资源消耗为 $c_1$，训练耗时为 $t_1$；若采用配置 2，资源消耗为 $c_2$，训练耗时为 $t_2$。资源统一按照“CPU 核心数 + GPU 显存 GB”计量，集群可使用的总资源量为 $C$。

现在要为每个任务选定一套配置，且每个任务只能选择两套之一。所有任务资源消耗的总和不得超过 $C$。在这些合法选择中，目标是最小化所有任务的总训练耗时，并进一步确定最优方案实际消耗的资源量以及未被使用的剩余资源量。

如果多个合法方案具有相同的最小总训练耗时，则取其中实际资源消耗最少的一个作为最终方案。

约束条件：

• 任务数量 $n$ 在 1 到 100 之间。
• 总资源上限 $C$ 在 1 到 1000 之间。
• 每个任务的 $c_1$、$t_1$、$c_2$、$t_2$ 均为 1 到 100 之间的正整数。

输入描述

第一行给出两个整数 $n$ 和 $C$，依次代表任务数量和总资源上限。

接下来的 $n$ 行中，第 $i$ 行包含四个正整数 $c_1$、$t_1$、$c_2$、$t_2$，分别对应该任务配置 1 的资源消耗、配置 1 的训练耗时、配置 2 的资源消耗、配置 2 的训练耗时。

输出描述

输出共三个整数，用单个空格分隔，依次为：满足资源限制的最小总训练耗时；该最小耗时方案中实际使用的资源总量；以及 $C$ 减去该实际使用资源量后的剩余资源。

样例1

输入

3 10
4 5 2 3
3 4 5 2
1 2 2 2

输出

7 8 2

说明

任务 1 选择配置 2，资源消耗为 $2$，耗时 $3$；任务 2 选择配置 2，资源消耗为 $5$，耗时 $2$；任务 3 选择配置 1，资源消耗为 $1$，耗时 $2$。

总资源消耗为 $2+5+1=8$，不超过 $C=10$；总耗时为 $3+2+2=7$。每个任务各自的最小耗时之和为 $3+2+2=7$，所以无法再降低总耗时。

任务 3 两种配置耗时相同，配置 1 的资源更少，因此选择配置 1。剩余资源为 $10-8=2$。

样例2

输入

1 1
1 5 2 3

输出

5 1 0

说明

总资源上限为 1。任务 1 的配置 1 资源消耗为 1，可以放入；配置 2 资源消耗为 2，超过上限，不可行。

因此唯一合法选择是配置 1，总耗时 5，实际消耗资源 1，剩余资源 $1-1=0$。

样例3

输入

2 5
3 4 2 6
2 5 4 1

输出

9 5 0

说明

所有不超过资源上限的选择中，总耗时最少的是：任务 1 选择配置 1，任务 2 选择配置 1。

该方案资源消耗为 $3+2=5$，总耗时为 $4+5=9$，刚好等于资源上限。

若任务 1 选择配置 2，任务 2 选择配置 1，则总耗时为 $6+5=11$，资源消耗为 $2+2=4$，虽然资源更少但耗时更大。

其他方案例如任务 2 选择配置 2 会超过资源上限。因此最优输出依次为 9、5、0。

样例4

输入

3 1000
10 20 5 25
3 15 4 15
6 7 2 12

输出

42 19 981

说明

资源上限 1000 很充足，可以在每个任务上独立选择耗时更小的配置。

任务 1 选择配置 1，耗时 20，资源 10。任务 2 两种配置耗时都为 15，选择资源更少的配置 1，资源 3。任务 3 选择配置 1，耗时 7，资源 6。

总耗时为 $20+15+7=42$，总资源消耗为 $10+3+6=19$，剩余资源为 $1000-19=981$。