cutbyhalf

Pasit wants to eat an apple, so he goes to his garden to collect apples from his trees.

There are a total of N apple trees labeled from 1 to N, and each tree produces exactly one apple. Initially, none of the trees have grown any apples. Each tree requires a certain number of days to grow its apple.

Pasit has M units of fertilizer. Each unit of fertilizer can be applied to any tree at any time, and a tree can receive any number of fertilizer units. Applying one unit of fertilizer to a tree reduces its remaining growth time from t to ⌈t / 2⌉ (i.e., the value is rounded up).

All trees grow simultaneously.

Pasit wants to know the minimum number of days he must wait until all N apples are ready, assuming he uses the fertilizer optimally.

Input Format

The first line contains two integers, N and M.

The second line contains N non-negative integers. The i^th integer represents the number of days required for the i^th tree to grow its apple.

It can be assumed that each tree requires less than 10⁹ days to grow.

Output Format

Output a single integer: the minimum number of days required for all apples to be ready.

Subtasks

• Subtask 1: Sample test cases (0 points)
• Subtask 2: N ≤ 1000, M ≤ 10000 (40 points)
• Subtask 3: N ≤ 10⁶, M ≤ 10⁷ (60 points)

Sample Test Case

Input:
6 7
6 7 6 7 6 7

Output:
19