题目描述

鸡国国王菜虚鲲为了表彰鸡国每一只鸡在过去一年的优秀表现，打算在接下来的 \(n\) 天中每天给鸡国的一只鸡发 \(1\) 袋或者 \(2\) 袋“鸡币”（鸡国的通用货币）作为福利。菜虚鲲要求每天来领钱鸡互不相同，即来领过钱的鸡不能再来，否则将受到严厉的处罚。

但聪明的鸡国老百姓侦察后发现菜虚鲲每天发的钱袋子里面装的钱数量是不一样的（同一天的相同），第 \(i\) 天发的每一袋钱为 \(a_i\) 元。如果第 \(i\) 天来领钱的鸡领 \(1\) 袋钱，它可以获得\(a_i\)元的“鸡币”，如果它领 \(2\) 袋钱，则可以获得\(2×a_i\)元“鸡币”，当然它也可以放弃，则第 \(i\) 天的钱菜虚鲲收回国库。

由于鸡国生活条件优越和鸡的贪念等原因，当第 \(i\) 天领钱的鸡同时满足以下两个条件时它才会感到幸福：

\(1.\) 领到的钱不能低于鸡国的平均收入\(m\)元。

\(2.\) 要跟它前面领了钱且感到幸福的鸡一样幸福或者更幸福。

仁慈的国王菜虚鲲希望鸡国的每一只鸡都能感到幸福，请你帮菜虚鲲规划一下在这 \(n\) 天中怎样给每一只发钱才能让最多的鸡感到幸福?

格式

输入格式

输入共 \(2\) 行。

第 \(1\) 行输入两个整数 \(n\) 和 \(m\)，分别表示发钱的天数（或理解为来领钱的鸡数）和鸡国的平均收入。

第 \(2\) 行 \(n\) 个正整数 \(ai\) (\(1≤i≤n\))，依次表示第 \(i\) 天发的一袋钱中的“鸡币”为\(a_i\)元。

输出格式

输出 \(1\) 行一个整数，表示最多可以让多少只鸡感到幸福。

样例1

样例输入1

2 1
2 1

样例输出1

2

样例2

样例输入2

3 2
1 2 3

样例输出2

3

样例3

样例输入3

6 4
1 2 1 2 1 5

样例输出3

3

样例1解释

可以让第 \(1\) 天来领钱的第 \(1\) 只鸡领 \(2\) 元（\(1\) 袋），第 \(2\) 天来领钱的第 \(2\) 只鸡领 \(2\) 元（\(2\) 袋），最多可以有 \(2\) 只鸡感到幸福。

样例2解释

由于鸡国的平均收入为 \(2\) 元，所以领 \(1\) 元及以下的鸡是不会感到幸福。可以让第 \(1\) 天来领钱的第 \(1\) 只鸡领 \(2\) 元（\(2\) 袋），第 \(2\) 天来领钱的第 \(2\) 只鸡领 \(2\) 元（\(1\) 袋），第 \(3\) 天来领钱的第 \(3\) 只鸡领 \(3\) 元（\(1\) 袋），最多可以有 \(3\) 只鸡感到幸福。

样例3解释

由于鸡国的平均收入为 \(4\) 元，所以第 \(1\) 天，第 \(3\) 天，第 \(5\) 天来领钱的鸡不管领 \(1\) 袋钱，或者领 \(2\) 袋钱，或者不领都不会感到幸福。可以让第 \(2\) 天来领钱的第 \(2\) 只鸡领 \(4\) 元（\(2\) 袋），第 \(4\) 天来领钱的第 \(4\) 只鸡领 \(4\) 元（\(2\) 袋），第 \(6\) 天来领钱的第 \(6\) 只鸡领 \(5\) 元（\(1\) 袋），最多可以有 \(3\) 只鸡感到幸福。

限制

\(30\%\)的数据：\(1≤n≤1000\)；

\(70\%\)的数据：\(1≤n≤10^4\)；

\(100\%\)的数据：\(1≤n≤10^6，1≤m≤10^9，1≤ai≤10^9\)。