D - Choosing Souvenirs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は旅行先のお土産屋さんで買い物をしています。お土産屋さんには N 種類の商品が並んでおり、i 番目の商品の重さは w_i グラム、満足度は v_i、在庫数は c_i 個です。高橋君は各商品を 0 個以上 c_i 個以下の任意の個数だけ購入できます。

高橋君は、帰りの飛行機で預ける荷物の重量をぴったり規定値に合わせたいと考えています。具体的には、購入する商品の重さの合計がちょうど S グラムになるようにしたいです。ここで、重さの合計とは、各商品について（その商品の重さ）×（購入個数）を求め、それらをすべて足し合わせた値のことです。

重さの合計をちょうど S グラムにすることが可能かどうかを判定してください。可能であれば、そのときの満足度の合計の最大値を出力してください。ここで、満足度の合計とは、各商品について（その商品の満足度）×（購入個数）を求め、それらをすべて足し合わせた値のことです。不可能であれば -1 を出力してください。

なお、どの商品も購入しない（すべての商品の購入個数が 0 個）という選択も許されます。この場合、重さの合計および満足度の合計はともに 0 です。

制約

  • 1 \leq N \leq 100
  • 1 \leq S \leq 30000
  • 1 \leq w_i \leq 30000
  • 1 \leq v_i \leq 10^4
  • 1 \leq c_i \leq 10^5
  • 入力はすべて整数である。

入力

N S
w_1 v_1 c_1
w_2 v_2 c_2
\vdots
w_N v_N c_N
  • 1 行目には、商品の種類数 N と、目標の重さの合計 S が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、i 番目の商品の重さ w_i、満足度 v_i、在庫数 c_i が、スペース区切りで与えられる。

出力

重さの合計をちょうど S グラムにできる場合は、満足度の合計の最大値を 1 行で出力せよ。不可能な場合は -1 を 1 行で出力せよ。

入力例 1

3 10
2 3 3
3 5 2
5 8 1

出力例 1

16

入力例 2

2 7
4 10 1
6 20 1

出力例 2

-1

入力例 3

8 100
6 12 5
10 20 3
15 35 4
22 45 2
7 9 10
30 80 1
11 25 6
18 40 3

出力例 3

240

入力例 4

20 5000
37 120 100
123 500 30
256 900 20
511 2000 10
1024 4100 4
999 3000 6
75 250 50
48 160 70
300 1000 15
450 1800 8
17 40 200
620 2500 5
840 3100 3
1500 7000 2
2300 9000 1
5 9 1000
199 800 25
333 1200 12
777 2800 4
12000 5000 10

出力例 4

22067

入力例 5

1 30000
1 10000 100000

出力例 5

300000000

Score : 400 pts

Problem Statement

Takahashi is shopping at a souvenir shop at his travel destination. The shop has N types of products, where the i-th product has a weight of w_i grams, a satisfaction value of v_i, and a stock of c_i items. Takahashi can purchase any number of each product from 0 to c_i inclusive.

Takahashi wants to make the total weight of his purchases exactly match a specified value for his checked baggage on the return flight. Specifically, he wants the total weight of the purchased products to be exactly S grams. Here, the total weight is the sum of (weight of each product) × (number purchased) over all products.

Determine whether it is possible to make the total weight exactly S grams. If it is possible, output the maximum total satisfaction. Here, the total satisfaction is the sum of (satisfaction of each product) × (number purchased) over all products. If it is impossible, output -1.

Note that choosing not to purchase any product (i.e., purchasing 0 of every product) is also allowed. In this case, both the total weight and total satisfaction are 0.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq S \leq 30000
  • 1 \leq w_i \leq 30000
  • 1 \leq v_i \leq 10^4
  • 1 \leq c_i \leq 10^5
  • All input values are integers.

Input

N S
w_1 v_1 c_1
w_2 v_2 c_2
\vdots
w_N v_N c_N
  • The first line contains the number of product types N and the target total weight S, separated by a space.
  • The following N lines each contain, for the i-th product, its weight w_i, satisfaction v_i, and stock c_i, separated by spaces.

Output

If it is possible to make the total weight exactly S grams, output the maximum total satisfaction in one line. If it is impossible, output -1 in one line.

Sample Input 1

3 10
2 3 3
3 5 2
5 8 1

Sample Output 1

16

Sample Input 2

2 7
4 10 1
6 20 1

Sample Output 2

-1

Sample Input 3

8 100
6 12 5
10 20 3
15 35 4
22 45 2
7 9 10
30 80 1
11 25 6
18 40 3

Sample Output 3

240

Sample Input 4

20 5000
37 120 100
123 500 30
256 900 20
511 2000 10
1024 4100 4
999 3000 6
75 250 50
48 160 70
300 1000 15
450 1800 8
17 40 200
620 2500 5
840 3100 3
1500 7000 2
2300 9000 1
5 9 1000
199 800 25
333 1200 12
777 2800 4
12000 5000 10

Sample Output 4

22067

Sample Input 5

1 30000
1 10000 100000

Sample Output 5

300000000