8582: Watches

内存限制:256 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

NIO is the boss of the watch shop. One day, he wants to purchase a batch of watches from the manufactory. However, he lives in Amefica(not a real country), a country in is heavily taxed. If he buys k watches, the i-th (starts from 1) watch in his list will cost him ai (the original price) plus k×i dollars (the i-th one in the original list) . Now NIO only has M dollars, so NIO asks you how many watches he can purchase actually.

输入格式

The first line contains two integers N,M, denoting the number of watches he would like to buy and the amount of money NIO has, respectively. The second line contains N integers, ai represents that the price of the i-th watch in the list.
1≤N≤105,1≤M≤105,1≤ai≤105

输出格式

Output a number, representing the maximum number of watches that NIO can purchase.

输入样例 复制

4 5
3 4 5 6

输出样例 复制

1