atcoder#DPX. Tower
Tower
配点 : 点
問題文
個のブロックがあります。 ブロックには と番号が振られています。 各 () について、ブロック の重さは で、丈夫さは で、価値は です。
太郎君は、 個のブロックのうち何個かを選び、それらを任意の順序で一列に積み重ね、塔を作ることにしました。 このとき、塔は次の条件を満たさなければなりません。
- 塔に含まれる各ブロック について、ブロック より上に積まれたブロックの重さの総和は 以下である。
塔に含まれるブロックの価値の総和の最大値を求めてください。
制約
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
出力
塔に含まれるブロックの価値の総和の最大値を出力せよ。
3
2 2 20
2 1 30
3 1 40
50
上から順にブロック と積み重ねると、この塔は条件を満たします。 塔に含まれるブロックの価値の総和は となります。
4
1 2 10
3 1 10
2 4 10
1 6 10
40
上から順にブロック と積み重ねればよいです。
5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
5000000000
答えは 32-bit 整数型に収まらない場合があります。
8
9 5 7
6 2 7
5 7 3
7 8 8
1 9 6
3 3 3
4 1 7
4 5 5
22
例えば、上から順にブロック と積み重ねればよいです。