{"problem":{"name":"Tower","description":{"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$. Taro has decided to build a tower by cho","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_x"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   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$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_x","tags":[],"sample_group":[["3\n2 2 20\n2 1 30\n3 1 40","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$."],["4\n1 2 10\n3 1 10\n2 4 10\n1 6 10","40\n\nBlocks $1, 2, 3, 4$ should be stacked in this order from top to bottom."],["5\n1 10000 1000000000\n1 10000 1000000000\n1 10000 1000000000\n1 10000 1000000000\n1 10000 1000000000","5000000000\n\nThe answer may not fit into a 32-bit integer type."],["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","22\n\nWe should, for example, stack Blocks $5, 6, 8, 4$ in this order from top to bottom."]],"created_at":"2026-03-03 11:01:14"}}