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 翻译