← 返回题目列表

AtCoder · abc442_g

G. 轻型背包

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

分数: 600 点

问题陈述

有 N 项目类型。 的 i-第类型的项目有 重量 W_i 和 值 V_i,你有 其中 K_i 。

从这些项目中选择一些(可能是零)项目时 K_1+\dots+K_N 物品的总重量不超过 C,找到所选项目的最大可能总价值。

约束

  • 1\leq N \leq 2\times 10^5
  • 1\leq C \leq 2\times 10^9
  • 1\leq W_i \leq 3
  • 1\leq V_i \leq 10^9
  • 1\leq K_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N C
W_1 V_1 K_1
W_2 V_2 K_2
\vdots
W_N V_N K_N

输出

打印答案。


示例输入 1

4 7
3 5 5
1 2 4
2 7 1
2 1 2

示例输出 1

16

如果您选择 1 项目 1-st 型, 2 的项目 2-nd 类型,以及 1 项目 3-rd型,总重量为 3\times 1+1\times 2+2\times 1=7\ (\leq C) 和 总价值是 5\times 1+2\times 2+7\times 1=16,这是最大值。


示例输入 2

2 1
3 442 442
2 442 442

示例输出 2

0

您无法选择任何项目。


示例输入 3

15 913575467
1 60505998 818008580
2 121011861 138996221
3 181517958 501899080
1 60506027 840594328
3 181517875 350034067
1 60505924 155374934
3 181517816 910748511
1 60506042 545531545
3 181517877 797829355
3 181517837 164163676
1 60505894 353195922
1 60505912 954291757
1 60506022 160449218
3 181517873 404011431
1 60506043 782177068

示例输出 3

55276836358648682