Score : 100 points
There are N blocks, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N), Block i has a weight of w_i, a solidness of s_i and a value of v_i.
Taro has decided to build a tower by choosing some of the N blocks and stacking them vertically in some order. Here, the tower must satisfy the following condition:
Find the maximum possible sum of the values of the blocks contained in the tower.
Input is given from Standard Input in the following format:
N w_1 s_1 v_1 w_2 s_2 v_2 : w_N s_N v_N
Print the maximum possible sum of the values of the blocks contained in the tower.
3 2 2 20 2 1 30 3 1 40
50
If Blocks 2, 1 are stacked in this order from top to bottom, this tower will satisfy the condition, with the total value of 30 + 20 = 50.
4 1 2 10 3 1 10 2 4 10 1 6 10
40
Blocks 1, 2, 3, 4 should be stacked in this order from top to bottom.
5 1 10000 1000000000 1 10000 1000000000 1 10000 1000000000 1 10000 1000000000 1 10000 1000000000
5000000000
The answer may not fit into a 32-bit integer type.
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
We should, for example, stack Blocks 5, 6, 8, 4 in this order from top to bottom.