题目描述

年度练兵一共持续 $D$ 天。开始时，小明的体力值为 $0$。每天开始时，他的体力值会变为前一天结束时体力值的一半，并向下取整。第一天开始时也进行这一步。

小明共有 $N$ 包补给，第 $i$ 包补给可以增加 $A_i$ 点体力。补给必须严格按照编号从小到大食用，每包最多食用一次。每天体力减半后，小明可以连续食用任意数量的下一包补给，也可以不食用。

一天的体力值是当天食用补给后的体力值。请安排食用补给的时间，使 $D$ 天中最低的体力值尽可能大，并输出这个最大值。补给不要求全部吃完。

输入格式

第一行包含两个整数 $N,D$，分别表示补给数量和练兵天数。

接下来 $N$ 行，第 $i$ 行包含一个整数 $A_i$，表示第 $i$ 包补给增加的体力值。

输出格式

输出一个整数，表示最低体力值能够达到的最大值。

5 5
10
40
13
22
7

24

数据范围与提示

• $1 \le N,D \le 50000$
• $1 \le A_i \le 10^6$