Stan Ford 是一名典型的大学毕业生，这意味着他最关心的事情之一就是下一顿饭在哪里吃。幸运的是，他受邀参加了一场由其研究团队的某些企业赞助商举办的多道菜烧烤聚会，每道菜正好持续一小时。

Stan 有点分析型人格，他确定了自己在连续几小时内的进食模式总是非常一致。在第一个小时，他最多可以吃 $m$ 卡路里的食物（其中 $m$ 取决于压力、生物节律、行星位置等因素），但之后每个小时，他能吃的量都会减少到原来的三分之二（小数部分总是向下取整）。然而，如果他有一个小时不吃东西，那么在接下来的一个小时里，他能吃的量将恢复到他停止进食前的水平。例如，如果 $m = 900$，并且他连续吃了五个小时，那么他每小时最多能吃的量分别是 $900, 600, 400, 266$ 和 $177$ 卡路里。但是，如果他在第三个小时没有吃东西，那么他在这几个小时里分别能吃 $900, 600, 0, 600$ 和 $400$ 卡路里。此外，如果 Stan 能连续两个小时不吃东西，那么在那之后的一个小时，他又能够吃 $m$ 卡路里的食物。在上面的例子中，如果 Stan 在第三和第四个小时没有吃东西，那么他可以摄入 $900, 600, 0, 0$ 和 $900$ 卡路里。

Stan 正在等待了解烧烤聚会每小时供应什么食物，因为他意识到菜单将决定他何时以及多久应该停止进食。例如，如果烧烤持续 $5$ 小时，每小时供应的菜肴热量分别为 $800, 700, 400, 300, 200$ 卡路里，那么当 $m = 900$ 时，最佳策略是每小时都吃，总摄入量为 $800 + 600 + 400 + 266 + 177 = 2243$ 卡路里。然而，如果第三道菜的热量从 $400$ 卡路里减少到 $40$ 卡路里（某种低热量的芹菜菜肴），那么最佳策略是在第三个小时不吃东西——这会导致总摄入量为 $1900$ 卡路里。

面对即将到来的美食，Stan 感到非常困惑，以至于无法冷静思考。给定菜肴的数量和每道菜的热量，你能确定 Stan 最多能摄入多少卡路里的热量吗？

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$ ($n \le 100, m \le 20\,000$)，分别表示菜肴的数量和 Stan 在第一个小时能吃的热量。下一行包含 $n$ 个正整数，表示每道菜的热量。

输出格式

输出 Stan 最多能摄入的卡路里总数。

样例

输入 1

5 900
800 700 400 300 200

输出 1

2243

输入 2

5 900
800 700 40 300 200

输出 2

1900