[R41B]购物 - 代码源竞赛平台

时空限制

1S/512M

题目描述

apiadu 拥有 $W$ 元钱，他希望在商店中购买尽可能多的商品。

商店中共有 $n$ 种商品，其中第 $i$ 种商品的价格为 $a_i$ 元。每种商品只有一件。

请你计算 apiadu 最多能买到多少件商品。

格式

输入格式

第一行包含两个整数 $n$ 和 $W$，分别表示商品的种类数量和 apiadu 拥有的总钱数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每种商品的价格。

输出格式

输出一个整数，表示最多能购买的商品数量。

样例

样例输入 #1

3 10
5 3 4

样例输出 #1

2

样例解释 #1

apiadu 可以购买价格为 $3$ 和 $4$ 的商品，总花费为 $3+4=7 \le 10$，共购买 $2$ 件。 或者购买价格为 $3$ 和 $5$ 的商品，总花费 $8 \le 10$，也是 $2$ 件。 如果购买所有商品，总花费 $5+3+4=12 > 10$，无法购买。 因此最多能购买 $2$ 件。

数据规模

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le W \le 10^9$，$1 \le a_i \le 10^9$。