{"raw_statement":[{"iden":"problem statement","content":"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$.\nTaro 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$.\nFind the maximum possible sum of the values of items that Taro takes home."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N \\leq 100$\n*   $1 \\leq W \\leq 10^5$\n*   $1 \\leq w_i \\leq W$\n*   $1 \\leq v_i \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $W$\n$w_1$ $v_1$\n$w_2$ $v_2$\n$:$\n$w_N$ $v_N$"},{"iden":"sample input 1","content":"3 8\n3 30\n4 50\n5 60"},{"iden":"sample output 1","content":"90\n\nItems $1$ and $3$ should be taken. Then, the sum of the weights is $3 + 5 = 8$, and the sum of the values is $30 + 60 = 90$."},{"iden":"sample input 2","content":"5 5\n1 1000000000\n1 1000000000\n1 1000000000\n1 1000000000\n1 1000000000"},{"iden":"sample output 2","content":"5000000000\n\nThe answer may not fit into a 32-bit integer type."},{"iden":"sample input 3","content":"6 15\n6 5\n5 6\n6 4\n6 6\n3 5\n7 2"},{"iden":"sample output 3","content":"17\n\nItems $2, 4$ and $5$ should be taken. Then, the sum of the weights is $5 + 6 + 3 = 14$, and the sum of the values is $6 + 6 + 5 = 17$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}