1765: 我什么都愿意做
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：400
解决：107
题目描述
你在神滨市工匠区迷路了。在街头，有人向你推荐能带来幸运的“猫头鹰幸运水”，你没多想就喝了。一个名为菲莉希亚的魔法少女也喝了同样的猫头鹰幸运水。你们两人所到之处，遭遇的尽是些奇妙的幸运的事件，然而……
喝完幸运药水之后，你获得了n点幸运值，现在你想要消耗掉这n点幸运值并使其收益最大化。你有n个活动可以同时参加（每项活动只能参加一次），参加不同的活动会获得不同数量的收益，且每个活动会消耗一点幸运值，你该如何安排你的活动使得到的收益最大呢？
喝完幸运药水之后，你获得了n点幸运值，现在你想要消耗掉这n点幸运值并使其收益最大化。你有n个活动可以同时参加（每项活动只能参加一次），参加不同的活动会获得不同数量的收益，且每个活动会消耗一点幸运值，你该如何安排你的活动使得到的收益最大呢？
输入
一个整数n(1<=n<=100)，代表你的幸运值。
接下来一个整数t(1<=t<=10000)表示可以参加的活动数量，随后t个不超过1e8（即100000000）的正整数，分别代表第1到第t个活动会获得的收益。
接下来一个整数t(1<=t<=10000)表示可以参加的活动数量，随后t个不超过1e8（即100000000）的正整数，分别代表第1到第t个活动会获得的收益。
输出
一行一个整数，输入最大收益。
样例输入 复制
3
4 1 2 3 4样例输出 复制
9提示
建议使用较快的输入输出