/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
N 種類のアイテムがあります。 i 種類目のアイテムの 重み は W_i、価値 は V_i であり、あなたはこれを K_i 個持っています。
これらの K_1+\dots+K_N 個のアイテムの中から、重みの総和が C を超えないようにいくつか（0 個でもよい）を選ぶとき、選んだアイテムの価値の総和が最大でいくつになるか求めてください。
制約
- 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 個、2 種類目のアイテムを 2 個、3 種類目のアイテムを 1 個選ぶと、重みの総和は 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
Score : 600 points
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.
Sample Input 1
4 7 3 5 5 1 2 4 2 7 1 2 1 2
Sample 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.
Sample Input 2
2 1 3 442 442 2 442 442
Sample Output 2
0
You cannot choose any items.
Sample 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
Sample Output 3
55276836358648682