题目背景

第二届四川省青少年 C++ 算法设计大赛小学 4-5 年级组全省总决赛试题。数据为洛谷自造。

题目描述

小 X 制定了一个为期 $n$ 天的训练计划。通过合理的规划，预定对于第 $i$ 天，他可以通过训练获得 $a_i$ 的学习值。

但是计划往往赶不上变化，小 X 发现他每天所获得的学习值与他该天的学习状态产生着关联，我们用一个专注度 $S$ 和认真阈值 $m$ 来描述小 X 的学习状态：

• $S$ 的初值为 $0$；
• 对于任意一天，如果 $S$ 的值大于等于认真阈值 $m$，那么小 X 将会在该天获得双倍的学习值（即 $a_i\times 2$），并使得专注度 $S$ 减半（向下取整）；
• 对于任意一天，如果 $S$ 的值小于认真阈值 $m$，那么小 X 只能在该天获得一半的学习值（向下取整，即 $\lfloor \frac{a_i}{2} \rfloor$），并增加相当于 $a_i$ 的专注度。

小 X 想知道 $n$ 天后，他一共可以获得多少学习值。

输入格式

第一行两个整数 $n,m$ 分别表示训练为期的天数和认真阈值。

第二行 $n$ 个空格隔开的数 $a_i$，第 $i$ 个数表示预期的第 $i$ 天的学习值。

输出格式

一行一个整数，表示 $n$ 天后小 X 一共可以获得多少学习值。

5 50
70 30 60 40 50

230

提示

样例解释

• 第一天，$S=0<m$，所以获得 $35$ 学习值，专注度增加 $70$，变为 $70$。
• 第二天，$S=70>m$，所以获得 $60$ 学习值，专注度减少一半，变为 $35$。
• 第三天，$S=35<m$，所以获得 $30$ 学习值，专注度增加 $60$，变为 $95$。
• 第四天，$S=95>m$，所以获得 $80$ 学习值，专注度减少一半，变为 $47$。
• 第五天，$S=47<m$，所以获得 $25$ 学习值，专注度增加 $50$，变为 $97$。

所以，一共获得 $35+60+30+80+25=230$ 学习值。

数据范围及约定

对于 $100\%$ 的数据，$1\leq n\leq 1000$，$1\leq m,a_i\leq 10^6$。