题目描述

在假期里，有 $n$ 天时间需要消磨， dash 正好有一套小说，分为 $m$ 册。 dash 可以每天选择看一册或多册，当然也可以不看，小说必须从第一册开始按顺序阅读。看完第 $i$ 册小说后， dash 的欢乐值将会上升 $a_i$ 点（重复阅读不能多次增加欢乐值）。 dash 会在傍晚前看完小说，然后在晚上做作业，由于作业较多，在做作业的时候， dash 的欢乐值将会减半（若欢乐值为奇数，则会向下取整）。假期开始前， dash 的欢乐值为 $0$。

dash 希望假期中每天傍晚的欢乐值都能够保持在一个水平及之上。定义 欢乐值瓶颈 为假期中每一天傍晚欢乐值的最小值。请帮助 dash 分配每天看多少小说，使得 欢乐值瓶颈 达到最大。

输入格式

第一行：两个正整数表示 $n$ 和 $m$； 第二行：$m$ 个正整数表示 $a_1,a_2,···, a_m$。

输出格式

单个整数：表示 欢乐值瓶颈的最大值。

样例

3 6
1 2 3 4 5 6

10

解释#1

第一天看前四册，后两天每天看一册。

数据范围

• 对于 $100\%$ 的测试数据满足：$1≤n≤100000，1≤m≤100000$。
• $1≤a_i≤20000$。