2306 - 【入门】买苹果

通过次数

11

提交次数

16

Time Limit : 1 秒
Memory Limit : 128 MB

周周遇到了一个难题,它现在只有 m 元钱,商场里有 n 个苹果每个苹果有对应的标价。现在,周周想要用 m 元钱买到尽可能多的苹果。例如:

5 20
13 9 11 4 7

我们可以选择买价格为 4,7,9 的这三个苹果,没有超出 20 元的预算。很显然,20 元最多可以买到三个苹果。

Input

输入共有 2 行:

  • 第一行有两个整数 n,m 表示有 n 个苹果和 m 元钱

  • 第二行有 n 个由空格分隔的整数,分别表示每个苹果的价值

所有输入的数字均为不超过 100 的正整数

Output

输出一个整数,表示周周最多能买到的苹果数量

Examples

Input

5 20
13 9 11 4 7

Output

3

Hint

为了让我们买的苹果数量尽可能多,很显然,应该从价格低的苹果开始尝试购买,如果买了当前价格最低的苹果以后仍然没有超出钱数总和 m,则可以继续购买更贵的苹果,直到无法购买更多苹果为止。