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