2215: 玩具(toy)

内存限制:256 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

      商店正在出售小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。