题目描述

"舞台上结出丰硕的果实，可是大家太过柔嫩，必须有人来守护。由我来守护，永远， 无论多少次。"

大场奈奈是一位温柔体贴的舞台少女，放学时间，她经常为同学们用香蕉做点心，为 此她需要购买大量的香蕉。

学校门口有 $\red{n }$个水果摊，第 $\red{i }$个水果摊一串香蕉价格为 $\red{a_i，}$由于供应紧张（全用来 做点心了），每个水果摊每天只能买到一串香蕉，为了买到足够的香蕉，她每天要去好多 水果摊。也是由于供应紧张，每隔一天所有水果摊的价格都会上涨，第一天价格为 $\red{a_i，}$则 第二天变为 $\red{a_{i}+1，}$第三天变为 $\red{a_{i }+ 2，}$依次类推。

大场奈奈每天的预算有限，每天购买的价格总和不能超过 $\red{m，}$如果某天预算没有花 完，下一天也不能用这天剩下的钱。

由于每天涨价，总有一天她会买不起任意一串香蕉，她想知道在那一天之前，她一 共能买到多少串香蕉。

输入格式

第一行输入两个整数 $\red{n, m，}$表示一共有 $\red{n }$个水果摊，每天的预算为 $\red{m}$。

第二行输入 $\red{n }$个整数 $\red{a_i ，}$表示每个水果摊第一天的价格。

输出格式

输出一个整数，表示一共能买到多少串香蕉。

样例

输入样例

4 10
1 2 3 4

输出样例

17

提示

对于 $\red{30\% }$的数据：$\red{1 ≤}$ $\red{n ≤}$ $\red{10^3}$; $\red{1 ≤}$ $\red{a_i ≤}$ $\red{10^3}$; $\red{1 ≤}$ $\red{m ≤}$ $\red{10^3}$。

对于 $\red{60\% }$的数据：$\red{1 ≤}$ $\red{n ≤}$ $\red{10^5}$; $\red{1 ≤}$ $\red{a_i ≤}$ $\red{10^5}$; $\red{1 ≤}$ $\red{m ≤}$ $\red{10^5}$。

对于所有数据：$\red{1 ≤}$ $\red{n ≤}$ $\red{10^5}$; $\red{1 ≤}$ $\red{a_i ≤}$ $\red{10^9}$; $\red{1 ≤}$ $\red{m ≤}$ $\red{10^9}$。

其中有 $\red{20\% }$的数据：每个 $\red{a_i }$都相同。