The King
Time limit2sMemory limit128 MB
Pick any subset of up to 100 values from minus 3 to 3 so the sum of the chosen values raised to the given power 1 to 3 is as large as possible.
Problem
Long ago, in a country far away, there lived a king who ruled a large kingdom. He was a very clever king, but he had one weakness: he could count only up to three.
He did not think of this as a real drawback. Many of his wizards could count up to one hundred, and one or two of them, people said, up to one thousand. Then grief came to the kingdom. Barbarians who far outnumbered the royal army began to approach from every side, and the king had to make the most important decision of his life. He had to choose which of his sons to make generals, send to the borders, and put in charge of the army.
The king knew that some of his sons were as clever as he was, while others were quite stupid and would only lower the spirit of the army with their wrong decisions. More precisely, he knew the mental potential of each son, an integer from minus three to three (remember that the king could count only up to three). He also knew that the chance of his army defeating the barbarians is proportional to the sum of the powers of the mental potentials of the sons he makes generals. The exponent is a positive integer, the same for every son, and it does not exceed three either. So the king has to pick the sons that make this sum as large as possible.
The king cannot do the arithmetic himself. The second power of a number no greater than three (its square) can already be greater than three. So he asks you, his most intelligent wizard, to do the calculation.
Input
The first line contains the number of the king's sons, an integer no greater than one hundred.
The second line contains the exponent used in the formula for the chance of defeating the barbarians, a positive integer no greater than three.
The third line contains the mental potentials of the sons in order, all integers whose absolute value is no greater than three.
Output
Print one number, the largest possible chance of defeating the barbarians, measured as the sum described above. The king may also make nobody a general, and then the sum is 0.
Hint
In the first example the king should make his first and third sons generals. The chance of defeating the barbarians is then the sum of the cubes of their mental potentials, eight plus one, that is nine.