## Tower

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

These problems are from the atcoder DP contest, and were transferred onto DMOJ. All problem statements were made by several atcoder users. As there is no access to the test data, all data is randomly generated. If there are issues with the statement or data, please contact Rimuru or Ninjaclasher on slack.

There are blocks, numbered . For each , Block has a weight of , a solidness of , and a value of .

Taro has decided to build a tower by choosing some of the blocks and stacking them vertically in some order. Here, the tower must satisfy the following condition:

• For each Block contained in the tower, the sum of the weights of the blocks stacked above it is not greater than .

Find the maximum possible sum of the values of the blocks contained in the tower.

#### Constraints

• All values in input are integers.

#### Input Specification

The first line will contain the integer .

The next lines will each contain three integers, .

#### Output Specification

Print the maximum possible sum of the values of the blocks contained in the tower.

#### Sample Input 1

3
2 2 20
2 1 30
3 1 40

#### Sample Output 1

50

#### Explanation For Sample 1

If Blocks are stacked in this order from top to bottom, this tower will satisfy the condition, with the total value of .

#### Sample Input 2

4
1 2 10
3 1 10
2 4 10
1 6 10

#### Sample Output 2

40

#### Explanation For Sample 2

Blocks should be stacked in this order from top to bottom.

#### Sample Input 3

5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000

#### Sample Output 3

5000000000

#### Explanation For Sample 3

The answer may not fit into a 32-bit integer type.

#### Sample Input 4

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

#### Sample Output 4

22

#### Explanation For Sample 4

We should, for example, stack Blocks in this order from top to bottom.