当前没有测试数据。

题目描述

小 $A$ 是某航空部队的一名战士，他报名参加了年度大练兵。

练兵共有 $D$ 天，每天有不同的项目，本次练兵的项目都设置在白天，晚上让大家休息。

小 $A$ 在练兵开始之前一共获得了 $N$ 包补给，第 $i$ 包补给吃下去之后，可以让小 $A$ 在当天获得值为 $A_i$ 的体力。如果第 $i$ 天白天演习结束后，小 $A$ 还有值为 $T_i$ 的体力值，由于晚上气温较低，第 $i+1$ 天，他的体力值将会下降到 $\lfloor T_i / 2 \rfloor$（即：$T_i / 2$ 向下取整的结果）。

小 $A$ 可以选择在任何一天吃掉补给，但练兵要求，每个人必须严格按照编号为 $1 \sim N$ 的顺序，吃掉自己的补给。

假设小 $A$ 在练兵开始时，体力值为 $0$。请设计一个吃掉补给的方案，使得小 $A$ 在 $D$ 天中，体力值最小的那一天的体力值，尽可能的大。

请编程计算出，在所有吃掉补给的方案中，小 $A$ 体力值最小的那天的体力值，最大是多少？

输入格式

第 $1$ 行输入 $2$ 个整数 $N$ 和 $D$。

接下来 $N$ 行，每行读入一个整数 $A_i$。

输出格式

输出小 $A$ 在 $D$ 天的演习中，体力值最小的那天的体力值，最大是多少。

样例

输入

5 5
10
40
13
22
7

输出

24

输入

5 8
24
27
39
38
18

输出

19

数据范围

对于 $30\%$ 的数据，满足 $1 \le N \le 50$，$1 \le D \le 10$。

对于 $100\%$ 的数据，满足 $1 \le N \le 5 \times 10^4$，$1 \le D \le 5 \times 10^4$，$1 \le A_i \le 10^6$。