解题思路

题目中 $N \le 15$，数据范围很小，但每个任务有两种资源约束：$CPU$ 和内存。 这类题最适合用 状态压缩动态规划。

先把每个任务看成一个二进制位，用一个状态 $mask$ 表示“选了哪些任务”。

1. 预处理单台服务器能否运行一个任务集合

题目内容

有 $N$ 个任务，需要把这些任务调度到服务器上运行。每个任务有 $CPU$ 需求 $c[i]$​，内存需求 $m[i]$​，任务价值 $v[i]$。

既有若干相同规格的服务器，内存规格为 $M$，$CPU$ 规格为 $C$，一台服务器可以运行多个任务并获得它们的总价值，条件是这些任务的 $CPU$ 需求之和不超过服务器的 $CPU$ 规格，且任务内存需求之和不超过服务器的内存规格。

一个任务只能运行在一台服务器上。

我们想知道，当服务器数量为 $1$ 到 $N$ 的每一种情况，其运行的最大任务最大总价值是多少，以帮助我们决策需要购买多少台服务器。

换句话说，对于 $K=1,2,…,N$，假设有 $K$ 台服务器，分别输出可运行的任务的最大总价值。

输入描述

第一行三个整数 $N,C,M（1≤N≤15，1≤C,M≤10^6）$，分别表示任务数量、服务器 $CPU$ 规格、服务器内存规格。

接下来 $N$ 行每行三个整数，$c[i]$ 和 $m[i]$ 和 $v[i]$ 表示每个任务的 $CPU$ 需求、内存需求、任务价值（$1≤c[i],m[i],v[i]≤10^6$）。

输出描述

输出 $N$ 行，每行一个整数，第 $i$ 行的整数表示服务器数量 $K=i$ 的时候的可运行的任务的最大总价值。

样例1

输入

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

输出

5
7
7

说明 当只有 $1$ 台服务器时，可以运行任务 $1$ 和 $3$，总价值为 $5$，（总 $CPU$ 需求为 $1+2=3$ 满足 $CPU$ 规格，总内存需求为 $4+6=10$，满足内存规格）。

当有 $2$ 台服务器时，第一台服务器运行任务 $1$ 和 $3$，第二台服务器运行任务 $2$，总价值为 $7$。

当有 $3$ 台服务器时，由于 $2$ 台服务器已经足够运行所有任务，故总价值依然为 $7$。

样例2

输入

1 5 5
10 10 100

输出

0

说明

只有 $1$ 台服务器和 $1$ 个任务，且任务的 $CPU$ / 内存需求大于服务器规格，则任务无法运行，总价值为 $0$ 。