题目内容

现有一批共 $N$ 个任务需要分配到若干台服务器上执行。所有服务器的规格完全相同，每台服务器拥有固定的 CPU 容量 $C$ 和内存容量 $M$。第 $i$ 个任务具有三个属性：CPU 需求 $c[i]$、内存需求 $m[i]$ 以及完成后能获得的价值 $v[i]$。

一台服务器可以同时承载多个任务，但必须满足以下条件：该服务器上所有任务的 CPU 需求总和不超过 $C$，且所有任务的内存需求总和不超过 $M$。此外，每个任务只能被分配给一台服务器，不能拆分到多台服务器上运行。

对于每一种服务器数量 $K = 1, 2, \dots, N$，需要计算在恰好拥有 $K$ 台服务器时，能够获得的最大总价值。这里的总价值是指所有成功被调度并运行的任务的价值之和。允许不运行某些任务，只要最终总价值最大即可。

约束条件：

• 任务数量 $N$ 满足 $1 \le N \le 15$。
• 服务器的 CPU 容量 $C$ 和内存容量 $M$ 均满足 $1 \le C, M \le 10^6$。
• 对于每一个任务 $i$，其 CPU 需求 $c[i]$、内存需求 $m[i]$ 和价值 $v[i]$ 均满足 $1 \le c[i], m[i], v[i] \le 10^6$。

输入描述

第一行包含三个整数 $N$、$C$、$M$，分别表示任务数量、每台服务器的 CPU 容量和内存容量。

接下来的 $N$ 行中，第 $i$ 行包含三个整数 $c[i]$、$m[i]$、$v[i]$，分别表示第 $i$ 个任务的 CPU 需求、内存需求和价值。

输出描述

输出共 $N$ 行。第 $K$ 行输出一个整数，表示当服务器数量为 $K$ 时，能够被调度任务的最大总价值。

样例1

输入

1 7 9
3 4 8

输出

8

说明

只有 1 台服务器，其容量为 CPU 7、内存 9。

任务需求为 CPU 3、内存 4，均不超过服务器容量，因此可以运行该任务，获得价值 8。

样例2

输入

2 5 5
3 3 5
3 3 6

输出

6
11

说明

当服务器数量 $K=1$ 时，一台服务器的总容量为 5。两个任务的 CPU 需求之和为 $3+3=6$，内存需求之和也为 $3+3=6$，都超过了容量 5，所以最多只能选择其中一个任务。

选择价值更高的第 2 个任务，得到价值 6。

当 $K=2$ 时，两台服务器可以分别运行两个任务，总价值为 $5+6=11$。

样例3

输入

3 4 4
2 2 3
3 1 5
1 3 6

输出

11
14
14

说明

当 $K=1$ 时，一台服务器的 CPU 和内存容量均为 4。任务 2 和任务 3 的 CPU 需求之和为 $3+1=4$，内存需求之和为 $1+3=4$，恰好可以同时放入一台服务器，获得价值 $5+6=11$。

其他任意两个任务的组合至少会在某一维上超过容量 4，因此一台服务器时的最大价值为 11。

当 $K=2$ 时，可以运行全部三个任务。例如将任务 1 单独放在一台服务器上，任务 2 和任务 3 放在另一台服务器上，总价值为 $3+5+6=14$。

当 $K=3$ 时，三台服务器仍然可以运行这三个任务，最大价值仍为 14。