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 or 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.
Comments