{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\u003cbr\u003e\n\n\u003cp\u003e\nYou have \u003cvar\u003eN\u003c/var\u003e kinds of items that you want to put them into a knapsack. Item \u003cvar\u003ei\u003c/var\u003e has value \u003cvar\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and weight \u003cvar\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e.\n\u003c/p\u003e\n\u003cp\u003e\nYou want to find a subset of items to put such that:\n\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eThe total value of the items is as large as possible.\u003c/li\u003e\n\u003cli\u003eThe items have combined weight at most \u003cvar\u003eW\u003c/var\u003e, that is capacity of the knapsack.\u003c/li\u003e\n\u003cli\u003eYou can select as many items as possible into a knapsack for each kind.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\nFind the maximum total value of items in the knapsack.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cpre\u003e\u003cvar\u003eN\u003c/var\u003e \u003cvar\u003eW\u003c/var\u003e\n\u003cvar\u003ev\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ew\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e\n\u003cvar\u003ev\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ew\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e\n:\n\u003cvar\u003ev\u003csub\u003eN\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ew\u003csub\u003eN\u003c/sub\u003e\u003c/var\u003e\n\u003c/pre\u003e\n\n\u003cp\u003e\nThe first line consists of the integers \u003cvar\u003eN\u003c/var\u003e and \u003cvar\u003eW\u003c/var\u003e. In the following lines, the value and weight of the \u003cvar\u003ei\u003c/var\u003e-th item are given.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nPrint the maximum total values of the items in a line.\n\u003c/p\u003e\n\n\u003ch2\u003eConstraints\u003c/h2\u003e\n\u003cul\u003e\n\u003cli\u003e 1 ≤ \u003cvar\u003eN\u003c/var\u003e ≤ 100\u003c/li\u003e\t\n\u003cli\u003e 1 ≤ \u003cvar\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e ≤ 1000\u003c/li\u003e\t\n\u003cli\u003e 1 ≤ \u003cvar\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e ≤ 1000\u003c/li\u003e\t\n\u003cli\u003e 1 ≤ \u003cvar\u003eW\u003c/var\u003e ≤ 10000\u003c/li\u003e\t\n\u003c/ul\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\u003cpre\u003e4 8\n4 2\n5 2\n2 1\n8 3\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 1\u003c/h2\u003e\n\u003cpre\u003e21\n\u003c/pre\u003e\n\u003cbr\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\u003cpre\u003e2 20\n5 9\n4 10\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 2\u003c/h2\u003e\n\u003cpre\u003e10\n\u003c/pre\u003e\n\u003cbr\u003e\n\n\u003ch2\u003eSample Input 3\u003c/h2\u003e\n\u003cpre\u003e3 9\n2 1\n3 1\n5 2\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 3\u003c/h2\u003e\n\u003cpre\u003e27\n\u003c/pre\u003e"}}]}