题目描述

从前，在一个遥远的国度，有一位国王统治着一个庞大的王国。这位国王非常聪明，但他有一个弱点——他只能数到$3$。尽管如此，他并不认为这是个大问题，因为他拥有许多能数到$100$的巫师（据说有些甚至能数到$1000$），所以一切还算顺利。

然而有一天，灾难降临了：数倍于王国的野蛮人从四面八方逼近。国王必须做出他一生中最重要的决定——选择哪些儿子担任将军，派往边境统帅军队。

国王知道，虽然他的某些儿子和他一样聪明，但有些却非常愚蠢，他们的错误决策只会打击军队士气。具体来说：

• 每个儿子的智力潜能是一个介于$-3$到$3$的整数（因为国王只能数到$3$）。
• 军队击败野蛮人的概率与被选为将军的儿子们的智力潜能的某次幂之和成正比（幂指数为正整数且不超过$3$）。

国王需要选择一组儿子，使得这个和最大化。但由于他无法计算超过$3$的数（例如$2^2=4>3$），他请求最聪明的巫师——也就是您——来解决这个问题。

输入输出

• 输入：
  • 第一行：国王的儿子数量$N$（不超过$100$）。
  • 第二行：幂指数$k$（$1 \leq k \leq 3$）。
  • 第三行：每个儿子的智力潜能（$|a_i| \leq 3$）。
• 输出：
  • 一个整数，表示最大的可能概率（即选中的儿子的智力潜能$k$次方和的最大值）。

示例

输入：

3  
3  
2 -1 1  

输出：

9  

解释：

• 选择第$1$个儿子（$2^3=8$）和第$3$个儿子（$1^3=1$），总和为$9$。
• 其他组合的和均不超过$9$。

来源

Northeastern Europe 2002, Northern Subregion