E. Santa Claus and Tangerines

发布时间:2016-12-31 7:16:56编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"E. Santa Claus and Tangerines ",主要涉及到E. Santa Claus and Tangerines 方面的内容,对于E. Santa Claus and Tangerines 感兴趣的同学可以参考一下。

E. Santa Claus and Tangerines
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Santa Claus has n tangerines, and the i-th of them consists of exactly ai slices. Santa Claus came to a school which has k pupils. Santa decided to treat them with tangerines.

However, there can be too few tangerines to present at least one tangerine to each pupil. So Santa decided to divide tangerines into parts so that no one will be offended. In order to do this, he can divide a tangerine or any existing part into two smaller equal parts. If the number of slices in the part he wants to split is odd, then one of the resulting parts will have one slice more than the other. It's forbidden to divide a part consisting of only one slice.

Santa Claus wants to present to everyone either a whole tangerine or exactly one part of it (that also means that everyone must get a positive number of slices). One or several tangerines or their parts may stay with Santa.

Let bi be the number of slices the i-th pupil has in the end. Let Santa's joy be the minimum among all bi's.

Your task is to find the maximum possible joy Santa can have after he treats everyone with tangerines (or their parts).

Input

The first line contains two positive integers n and k (1 ≤ n ≤ 106, 1 ≤ k ≤ 2·109) denoting the number of tangerines and the number of pupils, respectively.

The second line consists of n positive integers a1, a2, ..., an (1 ≤ ai ≤ 107), where ai stands for the number of slices the i-th tangerine consists of.

Output

If there's no way to present a tangerine or a part of tangerine to everyone, print -1. Otherwise, print the maximum possible joy that Santa can have.

Examples
Input
3 2
5 9 3


上一篇:《分布式事务解决之道》沙龙ppt共享
下一篇:【BZOJ 2618】 2618: [Cqoi2006]凸多边形 (半平面交)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款