Mini March Coding Challenge 2014
Tenri is getting ready to perform a magic show with magic boxes and sparklers. Because these boxes are strange and mysterious, each box can hold either zero or two other magic boxes (that are not within any other box yet) and any number of sparklers. Each box has a weight, determined by the formula:
where is the mysteriousness of the box, is the number of sparklers in it, and and are the weights of the two boxes within this box. If the box is completely empty, assume a value of infinity for . Tenri's magic show requires a single box which contains all the other boxes and sparklers either directly or indirectly. The overall impact for the magic show is the weight of the outermost box. Please determine the maximum impact Tenri's magic show can have.
The first line of input has 2 integers, and , the number of boxes and the number of sparklers Tenri has, respectively. is guaranteed to be an odd number. Each of the next lines contains a single positive integer less than or equal to , the mysteriousness value of box Tenri has.
Output the maximum possible impact Tenri's magic show can have.
Sample Input 1
3 2 1 1 2
Sample Output 1
Tenri can put the second and third of her boxes inside the first box, and then put two sparklers in the first box for an impact value of:
A diagram for this setup is as follows:
Sample Input 2
7 5 1 2 3 4 5 6 7
Sample Output 2