Mini March Coding Challenge 2014

Tenri is getting ready to perform a magic show with ~N~ ~(1 \le N \le 11)~ magic boxes and ~S~ ~(1 \le S \le 15)~ 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:

$$\displaystyle w = \min(w_i \times w_j, (m+s)^2) + s$$

where ~m~ is the mysteriousness of the box, ~s~ is the number of sparklers in it, and ~w_i~ and ~w_j~ are the weights of the two boxes within this box. If the box is completely empty, assume a value of infinity for ~w_i \times w_j~. Tenri's magic show requires a single box which contains all the other boxes and sparklers either directly or indirectly. The overall impact of the magic show is the weight of the outermost box. Please determine the maximum impact Tenri's magic show can have.

Input Specification

The first line of input has 2 integers, ~N~ and ~S~, the number of boxes and the number of sparklers Tenri has, respectively. ~N~ is guaranteed to be an odd number. Each of the next ~N~ lines contains a single positive integer less than or equal to ~10~, the mysteriousness value of ~i^{th}~ box Tenri has.

Output Specification

Output the maximum possible impact Tenri's magic show can have.

Sample Input 1

3 2
1
1
2

Sample Output 1

6

Explanation

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:

$$\displaystyle \min((\min(\infty, (1 + 0)^2) + 0) \times (\min(\infty, (2 + 0)^2) + 0), (1 + 2)^2) + 2 = 6$$

A diagram for this setup is as follows:

Sample Input 2

7 5
1
2
3
4
5
6
7

Sample Output 2

149

This problem statement is the exclusive and proprietary property of DMOJ. Any unauthorized use or reproduction of this information without the prior written consent of DMOJ is strictly prohibited. ©2014, DMOJ. All rights reserved.