← 返回题目列表

AtCoder · abc383_f

I. 多样性

中文机器翻译题面 查看原题

分数: 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