JPRSプログラミングコンテスト2026#1（AtCoder Beginner Contest 442）
翻译中…
Problem Statement
翻译中…
There are $N$ types of items. The $i$-th type of item has weight $W_i$ and value $V_i$, and you have $K_i$ of them.
翻译中…
When choosing some (possibly zero) items from these $K_1+\dots+K_N$ items so that the total weight does not exceed $C$, find the maximum possible total value of the chosen items.
翻译中…
Constraints
翻译中…
$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$- All input values are integers.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N C
W_1 V_1 K_1
W_2 V_2 K_2
\vdots
W_N V_N K_N翻译中…
Output
翻译中…
Print the answer.
翻译中…
样例
Input #1
4 7
3 5 5
1 2 4
2 7 1
2 1 2
Output #1
16
If you choose $1$ item of the $1$-st type, $2$ items of the $2$-nd type, and $1$ item of the $3$-rd type, the total weight is $3\times 1+1\times 2+2\times 1=7\ (\leq C)$ and the total value is $5\times 1+2\times 2+7\times 1=16$, which is the maximum.
Input #2
2 1
3 442 442
2 442 442
Output #2
0
You cannot choose any items.
Input #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
Output #3
55276836358648682
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。