{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e著名的背包问题。你正在准备去海边度假,只能携带一个容量为 S (1 \u003c\u003d S \u003c\u003d 2000) 的背包。你有 N (1 \u003c\u003d N \u003c\u003d 2000) 件物品可能想要带到海边。不幸的是,你无法将它们全部放入背包,所以你需要做出选择。对于每件物品,你都知道它的大小和价值。你希望最大化你要带来的所有物品的总价值。那么这个最大总价值是多少?\u003c/p\u003e\n\n\t\u003ch3\u003e输入\u003c/h3\u003e\n\t\u003cp\u003e第一行给出 S 和 N。接下来的 N 行,每行包含两个整数,描述其中一件物品。第一个数字是物品的大小,接下来的数字是物品的价值。\u003c/p\u003e\n\n\t\u003ch3\u003e输出\u003c/h3\u003e\n\t\u003cp\u003e你应该在一行上输出一个整数 - 你旅行中选择的物品的最大总价值。\u003c/p\u003e\n\n\t\u003ch3\u003e示例\u003c/h3\u003e\n\n\t\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 5\r\n1 8\r\n2 4\r\n3 0\r\n2 5\r\n2 3\r\n\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\u003c/div\u003e\n\u003c/div\u003e"}}]}