| 问题描述 |
|---|
有$$N$$件物品和一个容量为$$M$$的背包。 已知第$$i$$件物品的重量是$$w_i$$，价值是$$v_i$$。 求解如何选取物品才能使装入背包的物品价值总和最大。 注意：每件物品至多选取$$1$$次！
|
| 输入描述 |
第一行是两个正整数$$M,N$$分别代表背包的容量和物品的件数。（$$1 \le M \le 10^5，1 \le N \le 100$$） 接下来$$N$$行，每行两个正整数$$w_i,v_i$$分别表示第$$i$$件物品的重量和价值。（$$1 \le w_i,v_i \le 10^4$$）
|
| 输出描述 |
在一行中输出可以使得装入背包的物品价值总和达到最大，且字典序最小的物品选取方案。 输出时，每两个数字之间用空格隔开，最后一个数字后面没有空格。 |
| 样例输入复制样例 |
5 4 1 2 2 4 3 4 4 6 |
| 样例输出 |
1 4 |
| 提示说明 |
“1 4” 和 “2 3” 都可以使得装入背包的物品价值总和达到最大，但是 “1 4” 字典序最小。 |
| 相关 |