output_description: Print the maximum possible sum of the values of the blocks contained in the
  tower.
  
  * * *
input_description: 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
attempt: import sys
  
  sys.setrecursionlimit(2147483647)
  INF = 1 << 60
  MOD = 10**9 + 7  # 998244353
  input = lambda: sys.stdin.readline().rstrip()
  
  
  def resolve():
      n = int(input())
      WSV = [tuple(map(int, input().split())) for _ in range(n)]
      WSV.sort(key=lambda tup: tup[0] + tup[1])
  
      # dp[i][w] : i 番目まで見て、total weight が w のときの max value
      # solid_max <= 10^4 なので、total weight > 10^4 は考えなくて良い
      res = 0
      solid_max = 10**4
      dp = [-1] * (solid_max + 1)
      dp[0] = 0
  
      for w0, s0, v in WSV:
          for w in range(solid_max, -1, -1):
              if dp[w] == -1:
                  continue
              if w > s0:  # w <= s0
                  continue
              if w + w0 > solid_max:
                  res = max(res, dp[w] + v)
              else:
                  dp[w + w0] = max(dp[w + w0], dp[w] + v)
  
      res = max(res, max(dp))
      print(res)
  
  
  resolve()
  
problem_description: Statement
  
  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:
  
    * 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.
  
  Find the maximum possible sum of the values of the blocks contained in the
  tower.
samples: [{"input": "3\n    2 2 20\n    2 1 30\n    3 1 40", "output": "50\n    \n\nIf Blocks 2, 1 are stacked in this order from top to bottom, this tower will\nsatisfy the condition, with the total value of 30 + 20 = 50.\n\n* * *"}, {"input": "4\n    1 2 10\n    3 1 10\n    2 4 10\n    1 6 10", "output": "40\n    \n\nBlocks 1, 2, 3, 4 should be stacked in this order from top to bottom.\n\n* * *"}, {"input": "5\n    1 10000 1000000000\n    1 10000 1000000000\n    1 10000 1000000000\n    1 10000 1000000000\n    1 10000 1000000000", "output": "5000000000\n    \n\nThe answer may not fit into a 32-bit integer type.\n\n* * *"}, {"input": "8\n    9 5 7\n    6 2 7\n    5 7 3\n    7 8 8\n    1 9 6\n    3 3 3\n    4 1 7\n    4 5 5", "output": "22\n    \n\nWe should, for example, stack Blocks 5, 6, 8, 4 in this order from top to\nbottom."}]