3492 - 【SDX-F20】侠盗阿飞

题目描述

侠盗阿飞获得了一笔意外之财 w 元钱,他想用这笔钱去帮助需要帮助的人。现在知道有 n 个需要帮助的人以及他们每个人需要的钱数 xi 元(i=0,1,2,3,…..n-1),阿飞应该如何支配这笔钱使得能得到帮助的人数最多?

输入

第一行:两个数,阿飞的钱数 w,需要帮助的人数 n。

第二行:n 个数,分别表示第 i 个人需要的钱数 xi。

对于 30% 的数据,xi 为升序序列(x0<x1<x2<x3<…)

对于 100%的数据,0≤n≤500, 0<xi≤50000,0≤w≤2*10^9

输出

只有一个整数,表示阿飞最多能帮到的人数(最多的人数)。

样例

输入

10 5
1 2 3 4 5

输出

4

输入

1000 10
20 20 150 110 180 50 200 140 120 200

输出

9
来源

wms

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 67
通过人数 22
金币数量 2 枚
难度 未标记


上一题 下一题