题目描述

神犇航空开展了一项载客特技飞行业务。每次飞行长 $n$ 个单位时间，每个单位时间可以进行一项特技动作，可选的动作有 $k$ 种，每种动作有一个刺激程度 $c_i$。

如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为 (距上次该动作的时间) $\times c_i$，若为第一次进行该动作，价值为 $0$。

安排一种方案，使得总价值最大。

输入格式

第一行包含两个整数 $n, k$，如上所述；

第二行包含 $k$ 个整数，代表 $k$ 种动作的 $c_i$ 值。

输出格式

输出包含一行一个整数，代表最大总价值。

5 2
2 2

12

数据规模与约定

对于全部的测试点，保证 $1 \le n \le 10^3$，$1 \le k \le 300$，$0 \le c_i \le 10^3$。