{"problem":{"name":"Simple Knapsack","description":{"content":"You have $N$ items and a bag of strength $W$. The $i$\\-th item has a weight of $w_i$ and a value of $v_i$. You will select some of the items and put them in the bag. Here, the total weight of the sele","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc073_b"},"statements":[{"statement_type":"Markdown","content":"You have $N$ items and a bag of strength $W$. The $i$\\-th item has a weight of $w_i$ and a value of $v_i$.\nYou will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most $W$.\nYour objective is to maximize the total value of the selected items.\n\n## Constraints\n\n*   $1 ≤ N ≤ 100$\n*   $1 ≤ W ≤ 10^9$\n*   $1 ≤ w_i ≤ 10^9$\n*   For each $i = 2,3,...,N$, $w_1 ≤ w_i ≤ w_1 + 3$.\n*   $1 ≤ v_i ≤ 10^7$\n*   $W$, each $w_i$ and $v_i$ are integers.\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":"arc073_b","tags":[],"sample_group":[["4 6\n2 1\n3 4\n4 10\n3 4","11\n\nThe first and third items should be selected."],["4 6\n2 1\n3 7\n4 10\n3 6","13\n\nThe second and fourth items should be selected."],["4 10\n1 100\n1 100\n1 100\n1 100","400\n\nYou can take everything."],["4 1\n10 100\n10 100\n10 100\n10 100","0\n\nYou can take nothing."]],"created_at":"2026-03-03 11:01:13"}}