408371: GYM103107 K Keep Eating

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Keep Eatingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Megumi is a girl who likes to eat.

Today there will be a party at Aki's home. There are $$$N$$$ cakes for Megumi of different weight on the table. She will choose one cake and eat no more than half of it every time. But out of conscience, she won't eat those cakes whose weight is smaller than $$$K$$$.

However, she knows a magic to merge two cakes. That means she can put two cakes together and combine them into a larger cake whose weight is equal to the sum of weight of previous cakes.

Now Aki wants to know the maximum total weight of cakes Megumi can eat. Please note that she can eat as many times as she can, and each time the weight she eat is a positive integer no more than the half of the weight of cake.

Input

The first line contains two integers $$$N, K ~ (1 \leq N \leq 200\,000; ~ 2 \leq K \leq 10^6)$$$.

The second line contains $$$N$$$ integers $$$a_1, a_2, \cdots, a_n ~ (1 \leq a_i \leq 10^6)$$$ denoting the weight of each cake.

Output

Output one integer denoting the maximum total weight of cakes she can eat.

ExampleInput
5 10
9 8 7 10 10
Output
39

加入题单

上一题 下一题 算法标签: