Power Outlets

Interview

Time limit1sMemory limit1024 MB

Summary

Assign N devices with power-of-two charge times to M identical outlets to finish all charging as early as possible.

Level: Medium5 of 10
Topics: Greedy, Heap, Sorting, Implementation
Solved: No attempts yet

Problem

Gwangjae has started a business renting out electronic devices. Before going home for the day, he wants to charge N devices that he will lend to customers the next day. There are M available outlets, and all of them perform the same.

A device can charge from only one outlet at a time, and the time needed to charge is of the form 2k (0 ≤ k ≤ 15, k is an integer).

Find the minimum time needed to charge all the devices so that Gwangjae can go home early.

Input

The first line gives the number of devices N and the number of outlets M. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10)

The second line gives N integers representing the charging times t**i. (20 ≤ t**i ≤ 215, t**i = 2k (0 ≤ k ≤ 15, k is an integer))

Output

Print the minimum time needed to charge all the devices.

Examples1

Example 1
Input
```
5 2
1 4 4 8 1
```
Expected output
```
9
```