题目描述

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

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

输入格式

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

输出格式

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

3 6
1 2 3 4 5 6

10

样例解释 1

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

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 7$，$1\leq m\leq 7$；
• 对于 $60\%$ 的数据，$1\leq n\leq 500$，$1\leq m\leq 500$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100000$，$1\leq m\leq 100000$；
• $1\leq a_i\leq 20000$。