PEG Test – Oct 3rd, 2014

Firebending is an intense and aggressive bending art which uses concentrated barrages of fire, controlled by one's inner chi to overwhelm opponents. According to uncle Iroh, fire is the element of power. Of course, with great power comes great responsibility. Aang has just gained a new friend and firebending master, Zuko, to teach him the ways of the dragons.

In the past, Aang has attempted firebending on his own. However, due to a serious incident where he accidentally burned Katara, he's learned that fire is not to be toyed with. Ever since, Aang has been scared of firebending. Zuko realized what he must do – to teach Aang control. Only when Aang feels completely in control can his true training begin.

As an exercise, Zuko places ~N~ ~(1 \le N \le 10^4)~ leaves in front of Aang. He simultaneously sets all of the leaves on fire. Aang's job must be to control the burning rate of the leaves. The leaves all start burning from the inside. The ~i^\text{th}~ leaf ~(1 \le i \le N)~ will spend ~s_i~ ~(1 \le s_i \le 10^6)~ seconds burning before it is completely gone.

Aang is very new at this, and can only handle a certain amount of leaves at once. Throughout the entire exercise, he is currently only able to focus his chi onto at most ~K~ ~(1 \le K \le N)~ leaves. When Aang focuses on a leaf, the time it takes for the leaf to completely burn out will double. Aang will pick the ~K~ leaves at the beginning of the exercise and cannot switch after he's made the decision. Can you help Aang determine the time it takes for the first leaf to burn out?

Input Specification

Line 1: Two integers ~N~ and ~K~, respectively representing the number of total leaves and the number of leaves Aang can focus on controlling.
Line 2: ~N~ space-separated integers ~s_1, s_2, \dots, s_N~, representing the time it takes for each leaf to burn out without Aang's interference.

Output Specification

A single integer representing the number of seconds until the earliest leaf to burn out has fully burned out.

Sample Input 1

10 3
8 7 3 8 5 5 6 3 9 3

Sample Output 1

5

Sample Input 2

1 1
3

Sample Output 2

6