U544575 第二章：食物危机

#### 第二章：食物危机 $\,\,\,\,\,\,\,\,\,$ 神树族·地下蚁国才刚刚开始发展，就要面临一个难题：没有充足且长久的食物供应。这不，跪求一死就带着一群放哨以寻找物资去了。\ $\,\,\,\,\,\,\,\,\,$ 半路上，大家交流认为合适的解决方案：一只蚂蚁先发言："我觉得鼠妇（鼠妇，是一种节肢动物门-多足纲-等足目-卷甲虫科-卷甲虫属，俗称西瓜虫。鼠妇整体呈椭圆形，表面有光泽，身体卷曲时呈球形，形似西瓜，背腹扁平。）比较好，我们可以使用一片领土养殖鼠妇，鼠妇肉产量高，又比较美味。"一位蚂蚁立刻附和："好呀，不过搭配植物，更健康！"跪求一死听后，也笑着说："那这样，一片土养鼠妇，一片供应地下水，一片养殖玉露（一种地下植物，叶小），再搞一条道，可以运到地面，这样可以叫一批切叶蚁生产菌菇。这样可以吃鼠妇肉、玉露叶片、菌菇，还能喝水，怎么样！"大家一阵同意。\ $\,\,\,\,\,\,\,\,\,$ 不久，就找到了一株玉露，蚂蚁们把它连土挖出，搬运到蚁穴附近。然而，突然，地底一阵响动，应该是地底下有生物！跪求一死瞬间警觉起来！它仔细听着声音，听着像会挖洞的生物，大小至少有蚂蚁们的十倍！\ $\,\,\,\,\,\,\,\,\,$ 果然，一只蝼蛄爬了出来，一下扑向跪求一死。可跪求一死像是猜到了什么，瞬间使用镰刀猛蚁（一种特化蚁，节肢动物们-昆虫纲-膜翅目-蚁科-镰猛蚁属，Lv.7，擅长短距离的突袭）的绝招，瞬间穿刺，击杀了这只蝼蛄。\ $\,\,\,\,\,\,\,\,\,$ 可是击杀后，跪求一死发觉不对劲，这只蝼蛄的防御力未免也太低了吧！他仔细检查了蝼蛄的尸体，发觉有一大堆细小的咬痕，且咬痕正中要害！这应该是一批群居生物，甚至，可能是敌性的蚂蚁！\ $\,\,\,\,\,\,\,\,\,$ 跪求一死立马通知封锁了此处的隧道，并使用强力信息素标记了"未知危险"，带大家回去养鼠妇了。\ $\,\,\,\,\,\,\,\,\,$ 地下蚁国会碰上这支神秘的敌人蚂蚁部队吗？

$\,\,\,\,\,\,\,\,\,$ 有一个容量为$W$的食物仓库，有$n$个食物，第$i$个食物的大小为$w[i]$，美味值为$u[i]$。\ $\,\,\,\,\,\,\,\,\,$ 问：在仓库容的下的情况下，选哪些物品可以使美味值总和最大？

$\,\,\,\,\,\,\,\,\,$ 第一行 $2$ 个整数 $W$ , $n$ ，表示仓库容量和食物总数；\ $\,\,\,\,\,\,\,\,\,$ 接下来 $n$ 行，每行 $2$ 个整数， $w[i]$ 和 $u[i]$ ，表示大小与美味值。

$\,\,\,\,\,\,\,\,\,$ $2$ 行，第 $1$ 行是选择的食物编号（从 $1$ 到 $n$ 编号）；\ $\,\,\,\,\,\,\,\,\,$ 第 $2$ 行，表示最大美味值。

$\,\,\,\,\,\,\,\,\,$ 数据范围：\ $\,\,\,\,\,\,\,\,\,$ $1