# 优选猫咪

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

一位爱猫人士打算从按编号排列的猫咪中挑选固定数量。每只猫有一个评分，选择后的排列顺序由编号决定，越靠前的评分会获得越高的权重。

## 形式化问题描述

有 $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

### 输入

```text
5 3
1 -1 -2 -3 -4
```

### 输出

```text
4
```

### 样例 2

### 输入

```text
5 3
1 -7 -6 -5 -8
```

### 输出

```text
-14
```

### 样例 3

### 输入

```text
0 0

```

### 输出

```text
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% | 无额外条件 |