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

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

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

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

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

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

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

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

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

样例 1 解释

如果小 A 选择在第 1 天吃完自己所有的补给。

那么第 1 天小 A 的体力值 =10+40+13+22+7=92。

第 2 天小 A 的体力值 =92/2=46。

第 3 天小 A 的体力值 =46/2=23。

第 4 天小 A 的体力值 =23/2=11。

第 5 天小 A 的体力值 =11/2=5。

因此在这个方案下，小 A 体力值最小的那天的体力值为 5。

上述方案不是最优方案，最优方案可以按照下面的顺序吃掉补给：

第 1 天，小 A 吃掉 1,2 号补给，体力值 =10+40=50。

第 2 天，小 A 不吃补给，体力值 =50/2=25。

第 3 天，小 A 吃掉 3 号补给，体力值 =25/2+13=12+13=25。

第 4 天，小 A 吃掉 4 号补给，体力值 =25/2+22=12+22=34。

第 5 天，小 A 吃掉 5 号补给，体力值 =34/2+7=17+7=24。

在这个最优方案下，小 A 体力值最小的那天的体力值为 24，这个值是所有吃补给方案中，体力值最小那天的体力值的最大值，因此答案为 24。

数据范围

对于 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。

月赛二分