{"raw_statement":[{"iden":"problem statement","content":"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$.\nTaro 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:\n\n*   For each Block $i$ contained in the tower, the sum of the weights of the blocks stacked above it is not greater than $s_i$.\n\nFind the maximum possible sum of the values of the blocks contained in the tower."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N \\leq 10^3$\n*   $1 \\leq w_i, s_i \\leq 10^4$\n*   $1 \\leq v_i \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$w_1$ $s_1$ $v_1$\n$w_2$ $s_2$ $v_2$\n$:$\n$w_N$ $s_N$ $v_N$"},{"iden":"sample input 1","content":"3\n2 2 20\n2 1 30\n3 1 40"},{"iden":"sample output 1","content":"50\n\nIf 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$."},{"iden":"sample input 2","content":"4\n1 2 10\n3 1 10\n2 4 10\n1 6 10"},{"iden":"sample output 2","content":"40\n\nBlocks $1, 2, 3, 4$ should be stacked in this order from top to bottom."},{"iden":"sample input 3","content":"5\n1 10000 1000000000\n1 10000 1000000000\n1 10000 1000000000\n1 10000 1000000000\n1 10000 1000000000"},{"iden":"sample output 3","content":"5000000000\n\nThe answer may not fit into a 32-bit integer type."},{"iden":"sample input 4","content":"8\n9 5 7\n6 2 7\n5 7 3\n7 8 8\n1 9 6\n3 3 3\n4 1 7\n4 5 5"},{"iden":"sample output 4","content":"22\n\nWe should, for example, stack Blocks $5, 6, 8, 4$ in this order from top to bottom."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}