Kiana likes desserts. One day, she bought \(N\) slices of cake from the store to share with TinyTree. The cake slices can be numbered from \(1\) to \(N\), and the \(i^{th}\) slice has a integer size of \(A_i\).
Since each slice of cake has a different flavour, Kiana and TinyTree wants to cut each slice into two pieces, each of then taking one piece to taste. However, slicing cakes fairly is an age-old problem. After some negotiation, it was decided Kiana would slice the cakes with her knife, and TinyTree would get \(M\) opportunities to exercise 'cake selection rights'. Specifically, the two of them would proceed according to the following process:
Step 1: Kiana chooses a slice of cake which has not been cut, and cuts it into two pieces. The sizes of the resulting pieces are decided by Kiana, and can be any two nonnegative real numbers summing up to the size of the original slice.
Step 2: After TinyTree observes the sizes of the two cake pieces sliced by Kiana, if she has any 'cake selection rights' remaining she can choose whether or not to consume one such right.
Step 3: If TinyTree exercises 'cake selection rights', she can select one of the two cake pieces for herself, and the other will go to Kiana. Otherwise, Kiana selects one of the two cake pieces for herself, and the other goes to TinyTree. This process then repeats from Step 1 until all slices of cake have been eaten.
Kiana and TinyTree both want to maximise the sum of sizes of cake they receive, and will slice and select optimally to achieve this. What is the sum of sizes of cake that Kiana will obtain?
The first line of input consists of two integers \(N\) and \(M\), the number of slice of cake and the number of 'cake selection rights' accorded to TinyTree respectively.
The second line of input consists of \(N\) integers. The \(i^{th}\) integer denotes \(A_i\), the size of the \(i^{th}\) slice of cake.
Output a single real number, the sum of slices of cake Kiana will obtain, in decimal notation and with relative error no more than \(10^{-6}\).
| Subtask # | Score | Constraints |
|---|---|---|
| 1 | 8 | \(M = N\) |
| 2 | 28 | \(N \leq 10\) |
| 3 | 64 | No additional constraints |
| Sample Input 1 | Sample Output 1 |
4 3
|
5.250000
|
In this input example, there are 4 slices of cake and TinyTree has 3 opportunities to exercise 'cake selection rights'. One optimal solution is:
Round 1: Kiana chooses the slice with size 3, and cuts it into pieces with sizes 1.75 and 1.25. TinyTree exercises 'cake selection rights' and takes the piece with size 1.75. Kiana receives the piece with size 1.25.
Round 2: Kiana chooses the slice with size 1, and cuts it into pieces with sizes 0 and 1. TinyTree does not exercises 'cake selection rights'. Kiana takes the piece with size 1.
Round 3: Kiana chooses the slice with size 2, and cuts it into pieces with sizes 1 and 1. TinyTree exercises 'cake selection rights'. Both TinyTree and Kiana recieve a piece with size 1.
Round 4: Kiana chooses the slice with size 4, and cuts it into pieces with sizes 2 and 2. TinyTree exercises 'cake selection rights'. Both TinyTree and Kiana recieve a piece with size 2.
It can be proven that no other strategy will allow Kiana or TinyTree to get more cake if the other of them responds optimally.
| Subtask | Score |
|---|---|
| 1 | 8 |
| 2 | 28 |
| 3 | 64 |