output_description: Print the maximum possible sum of the values of items that Taro takes home.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N W
      w_1 v_1
      w_2 v_2
      :
      w_N v_N
attempt: #!/usr/bin/env python3
  import sys
  
  
  def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
      maxv=sum(v)+1
      dp=[[2**60]*maxv for _ in range(N+1)]
      dp[0][0]=0
      for i in range(N):
          for j in range(maxv):
              if j>=v[i]:
                  dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
              else:                                                                                                                                            empla
                  dp[i+1][j]=dp[i][j]                                                                                                                          te)
  
      ans=0
      for j in range(maxv):
          if W >= dp[N][j]:
              ans=j                                                                                                                                            empla
      print(ans)
      return
  
  
  # Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
  def main():
      def iterate_tokens():
          for line in sys.stdin:
              for word in line.split():
                  yield word
      tokens = iterate_tokens()
      N = int(next(tokens))  # type: int
      W = int(next(tokens))  # type: int                                                                                                                       empla
      w = [int()] * (N)  # type: "List[int]"
      v = [int()] * (N)  # type: "List[int]"                                                                                                                   15292
      for i in range(N):                                                                                                                                       46976
          w[i] = int(next(tokens))                                                                                                                             04606
          v[i] = int(next(tokens))                                                                                                                             52921
      solve(N, W, w, v)                                                                                                                                        76, 1
                                                                                                                                                               46068
  if __name__ == '__main__':                                                                                                                                   29215
      main()
problem_description: Statement
  
  There are N items, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N),
  Item i has a weight of w_i and a value of v_i.
  
  Taro has decided to choose some of the N items and carry them home in a
  knapsack. The capacity of the knapsack is W, which means that the sum of the
  weights of items taken must be at most W.
  
  Find the maximum possible sum of the values of items that Taro takes home.
samples: [{"input": "3 8\n    3 30\n    4 50\n    5 60", "output": "90\n    \n\nItems 1 and 3 should be taken. Then, the sum of the weights is 3 + 5 = 8, and\nthe sum of the values is 30 + 60 = 90.\n\n* * *"}, {"input": "1 1000000000\n    1000000000 10", "output": "10\n    \n\n* * *"}, {"input": "6 15\n    6 5\n    5 6\n    6 4\n    6 6\n    3 5\n    7 2", "output": "17\n    \n\nItems 2, 4 and 5 should be taken. Then, the sum of the weights is 5 + 6 + 3 =\n14, and the sum of the values is 6 + 6 + 5 = 17."}]