{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"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":"4 6\n2 1\n3 4\n4 10\n3 4"},{"iden":"sample output 1","content":"11\n\nThe first and third items should be selected."},{"iden":"sample input 2","content":"4 6\n2 1\n3 7\n4 10\n3 6"},{"iden":"sample output 2","content":"13\n\nThe second and fourth items should be selected."},{"iden":"sample input 3","content":"4 10\n1 100\n1 100\n1 100\n1 100"},{"iden":"sample output 3","content":"400\n\nYou can take everything."},{"iden":"sample input 4","content":"4 1\n10 100\n10 100\n10 100\n10 100"},{"iden":"sample output 4","content":"0\n\nYou can take nothing."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}