题目描述

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

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

输入格式