题目描述

代码勇者来到了金苹果岛上，金苹果岛上有两种苹果：随处可见的红苹果与稀有美味的金苹果。

勇者的初始代码能力为 $1$，他每吃下一个红苹果，代码能力就会得到一定程度的提升（每个红苹果带来的提升可能是不同的，甚至也可能是负的）；他每吃下一个金苹果，代码能力就会直接翻倍（每个金苹果的效果都是完全相同的）。

岛上的苹果仙子用 $n$ 个红苹果和 $m$ 个金苹果招待了勇者，勇者必须吃光所有苹果。勇者必须按照仙子规定的顺序吃红苹果，但是他可以自由安排什么时候吃金苹果（可以在吃任意一个红苹果之前或之后吃若干个金苹果）。

求勇者在离开金苹果岛的时候的代码能力的最大值。

输入格式

第一行输入两个正整数 $n$（$n \leq 10^5$）和 $m$（$m \leq 20$）。

第二行输入 $n$ 个正整数 $a_i$（$|a_i| \leq 10$）。

输出格式

输出一个整数，表示勇者在离开金苹果岛的时候的代码能力的最大值。

6 2
1 -2 3 1 -6 5

15

8 3
5 -3 -8 2 4 -11 9 1

42

提示

【样例 1 解释】

勇者吃掉红苹果 $1, -2, 3, 1$，代码能力变为 $4$；

勇者吃掉 $2$ 颗金苹果，代码能力变为 $16$；

勇者吃掉红苹果 $-6, 5$，代码能力变为 $15$。

这是勇者的最优方案。

【子任务】

::cute-table{tuack}

对于 $100\%$ 的数据，$n \leq 10^5$，$m \leq 20$，$|a_i| \leq 10$。