分数: 525 点
问题陈述
有 N 商店中出售的产品。的 i-第产品的价格为 P_i 日元,实用价值为 U_i和一种颜色 C_i.
您将选择其中的一些子集 N 要购买的产品(可能没有)。所选产品的总价不得超过 X 日元。
您的满意是 S + T \times K,其中 S 是所选产品的效用总和,并且 T 是所选产品中不同颜色的数量。在这里, K 是给定常数。
您将选择最大限度地满足您的产品。找到最大的满足感。
约束
- 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)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X K P_1 U_1 C_1 P_2 U_2 C_2 \vdots P_N U_N C_N
输出
打印答案。
示例输入 1
3 10 5 1 3 1 7 4 2 4 5 1
示例输出 1
17
如果您购买第 1 件和第 2 件产品,则总效用 S is 7,以及不同颜色的数量 T is 2。那么,您的满意度是 7 + 2 \times 5 = 17。没有一个购买计划能让您满意 18 或更大,所以答案是 17.
示例输入 2
5 30 3 5 4 3 11 20 1 9 10 4 7 5 2 16 15 4
示例输出 2
44
如果您购买第 2、3、4 个产品,则总效用 S is 35,以及不同颜色的数量 T is 3。那么,您的满意度是 35 + 3 \times 3 = 44。没有一个购买计划能让您满意 45 或更大,所以答案是 44.
示例输入 3
22 75 6426 9 309 9 5 470 5 17 481 12 27 352 14 1 191 18 7 353 20 9 99 15 20 401 17 46 434 19 11 459 22 10 317 19 15 440 18 17 438 19 25 461 22 5 320 22 1 476 21 11 315 3 8 112 9 11 438 13 19 362 8 10 422 13 10 152 21
示例输出 3
67717