{"problem":{"name":"Knapsack 1","description":{"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$. Taro has decided to choose some of the $N$ items and carry them ","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_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   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$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_d","tags":[],"sample_group":[["3 8\n3 30\n4 50\n5 60","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$."],["5 5\n1 1000000000\n1 1000000000\n1 1000000000\n1 1000000000\n1 1000000000","5000000000\n\nThe answer may not fit into a 32-bit integer type."],["6 15\n6 5\n5 6\n6 4\n6 6\n3 5\n7 2","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$."]],"created_at":"2026-03-03 11:01:14"}}