Maximizing Stunt Flight Total Excitement

Shenben Airlines is launching a new passenger-carrying stunt flight service. A flight lasts for n time units, and during each unit a stunt maneuver is performed. There are k available maneuvers with corresponding excitement levels \(c_i\). However, if the same maneuver is repeated consecutively the passengers get bored. Thus, the value of performing a maneuver at a given time is defined as:

[ \text{value} = \begin{cases} 0, & \text{if it is the first time the maneuver is performed},\ (\text{current time} - \text{last time this maneuver was performed}) \times c_i, & \text{otherwise.} \end{cases} ]

Your task is to schedule the maneuvers (i.e. choose an action for each of the n time units) so that the total value is maximized. Note that if a maneuver is performed more than once, its total contribution equals \((t_{last}-t_{first}) \times c_i\) regardless of the number of intermediate occurrences.

Observation: It is always optimal to perform each maneuver that you want to obtain a reward exactly twice: once early and once later, to maximize the time gap; any extra occurrence between the two does not increase the reward. However, you must assign all n time units with some maneuver, so extra time units may be filled arbitrarily with maneuvers that are already performed.

Hint: For each maneuver chosen (i.e. scheduled twice), if you assign its first occurrence at time \(f\) and its last occurrence at time \(\ell\), its contribution is \((\ell - f)\times c_i\). Since all time units are distinct, an optimal strategy is to choose a set of maneuvers (at most \(\lfloor \frac{n}{2} \rfloor\) if \(k\) is large) and assign their first occurrences to the smallest available times and their last occurrences to the largest available times. For the maneuver with the highest excitement level, you can ideally achieve a gap of \(n-1\), for the next one a gap of \(n-3\), and so on.

inputFormat

The first line contains two integers \(n\) and \(k\) (with \(n \ge 1\) and \(k \ge 1\)).

The second line contains \(k\) space-separated integers \(c_1, c_2, \dots, c_k\), where \(c_i\) is the excitement level of the i-th maneuver.

outputFormat

Output a single integer denoting the maximum total value (excitement) achievable.

sample

5 3
1 2 3

16