优选猫咪¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
一位爱猫人士打算从按编号排列的猫咪中挑选固定数量。每只猫有一个评分，选择后的排列顺序由编号决定，越靠前的评分会获得越高的权重。
形式化问题描述¶
有 \(n\) 只猫，第 \(i\) 只的评分为 \(v_i\) . 选择恰好 \(k\) 个不同下标，并按递增顺序记为 \(i_1<i_2<\cdots<i_k\) . 所得总分为
\[
\sum_{j=1}^{k}v_{i_j}3^{k-j}
\]
求能得到的最大总分。评分可以为负，不能因为负数而少选猫。\(k=0\) 时选择空集，总分为零；所选猫的顺序不能自行调整。
输入格式¶
第一行两个整数 \(n,k\) . 第二行 \(n\) 个整数 \(v_1,v_2,\ldots,v_n\) . 当 \(n=0\) 时第二行为空。
输出格式¶
输出一行一个整数，表示最大总分。
样例¶
样例 1¶
输入¶
5 3
1 -1 -2 -3 -4
输出¶
4
样例 2¶
输入¶
5 3
1 -7 -6 -5 -8
输出¶
-14
样例 3¶
输入¶
0 0
输出¶
0
样例解释¶
样例 1 选择评分 \(1,-1,-2\) ，得到 \(1\cdot9-1\cdot3-2=4\) .
样例 2 选择评分 \(1,-5,-8\) ，得到 \(1\cdot9-5\cdot3-8=-14\) ，这是合法的负答案。样例 3 选择空集。
数据范围与保证¶
对 100% 的数据：\(0\le k\le n\le25\) ，\(|v_i|\le1000\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |