AT_abc383_f [ABC383F] Diversity

在一家店里有 $N$ 个商品在售。第 $i$ 个商品的价格为 $P_i$ 日元，效用为 $U_i$，颜色为 $C_i$。 你可以从这 $N$ 个商品中选择若干个（可以为 $0$ 个）购买。此时，所购买商品的总价格不能超过 $X$ 日元。 你的满意度定义为：所购买商品的效用总和为 $S$，所购买商品的颜色种类数为 $T$，则满意度为 $S + T \times K$。其中，$K$ 是输入给定的常数。 请你选择购买哪些商品，使得你的满意度最大，并输出最大满意度。

输入以以下格式从标准输入给出。 > $N$ $X$ $K$ > $P_1$ $U_1$ $C_1$ > $P_2$ $U_2$ $C_2$ > $\vdots$ > $P_N$ $U_N$ $C_N$

请输出最大满意度。

## 限制条件 - $1 \leq N \leq 500$ - $1 \leq X \leq 50000$ - $1 \leq K \leq 10^9$ - $1 \leq P_i \leq X$（$1 \leq i \leq N$） - $1 \leq U_i \leq 10^9$（$1 \leq i \leq N$） - $1 \leq C_i \leq N$（$1 \leq i \leq N$） - 所有输入均为整数 ## 样例解释 1 当购买第 $1$ 个和第 $2$ 个商品时，效用总和 $S$ 为 $7$，颜色种类数 $T$ 为 $2$。因此，满意度为 $7 + 2 \times 5 = 17$。不存在能使满意度达到 $18$ 或更高的购买方式，所以答案为 $17$。 ## 样例解释 2 当购买第 $2$、第 $3$、第 $4$ 个商品时，效用总和 $S$ 为 $35$，颜色种类数 $T$ 为 $3$。因此，满意度为 $35 + 3 \times 3 = 44$。不存在能使满意度达到 $45$ 或更高的购买方式，所以答案为 $44$。 由 ChatGPT 4.1 翻译