{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e pre { text-align:left; font-family: \"Courier New\", Courier, monospace; font-size: 16px; white-space: pre; line-height:20px; text-indent: 0px; }\u003c/style\u003e\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003eGiven a set of n items, each with a weight w[i] and a value v[i], determine a way to choose the items into a knapsack so that the total weight is less than or equal to a given limit B and the total value is as large as possible. Find the maximum total value. (Note that each item can be only chosen once).\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003eThe first line contains the integer T indicating to the number of test cases.\u003c/p\u003e\n \u003cp\u003eFor each test case, the first line contains the integers n and B.\u003c/p\u003e\n \u003cp\u003eFollowing n lines provide the information of each item.\u003c/p\u003e\n \u003cp\u003eThe i-th line contains the weight w[i] and the value v[i] of the i-th item respectively.\u003c/p\u003e\n \u003cp\u003e1 \u0026lt;\u003d number of test cases \u0026lt;\u003d 100\u003c/p\u003e\n \u003cp\u003e1 \u0026lt;\u003d n \u0026lt;\u003d 500\u003c/p\u003e\n \u003cp\u003e1 \u0026lt;\u003d B, w[i] \u0026lt;\u003d 1000000000\u003c/p\u003e\n \u003cp\u003e1 \u0026lt;\u003d v[1]+v[2]+...+v[n] \u0026lt;\u003d 5000\u003c/p\u003e\n \u003cp\u003eAll the inputs are integers.\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003eFor each test case, output the maximum value.\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e1\r\n5 15\r\n12 4\r\n2 2\r\n1 1\r\n4 10\r\n1 2\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e15\u003c/pre\u003e"}}]}