2107: 玩具(toy)

题目描述


商店正在出售小C最喜欢的系列玩具,在接下来的n周中,每周会出售其中的一款,同一款玩具不会重复出现。
由于是小C最喜欢的系列,他希望尽可能多地购买这些玩具,但是同一款玩具小C只会购买一个。同时,小C的预算只有m元,因此他无法将每一款都纳入囊中。此外,小C不能连续两周都购买玩具,否则他会陷入愧疚。现在小C想知道,他最多可以买多少款不同的玩具呢?

输入


输入文件共2行;
第一行两个正整数n和m,中间用一个空格隔开;
第二行共n个正整数,第i个正整数表示第i周出售的玩具的价格。

输出


输出文件只有一行,包含一个整数,表示小C最多能买多少款不同的玩具。

样例输入


3 8
4 4 5

样例输出


1

提示


【数据范围】
对于30%的数据,n≤10;
对于60%的数据,n≤100,m≤1000;
对于100%的数据,n≤1000,m≤1000000,单个玩具的价格≤1000。

来源/分类


2019年海淀区挑战赛初中组

请先 登录 后评论
  • 0 关注
  • 0 收藏,575 浏览
  • 轩爸 提出于 2019-08-02 22:38