Background

1. wqs loves flight simulation.
2. clj founded Shenben Airlines (pinyin). Since clj also wants to play games, you are in charge of managing the company.

Note: This is just a fictional background and does not correspond to real/simulated flying.

Problem Description

Shenben Airlines (pinyin) has launched a passenger-carrying stunt flying service. Each flight lasts $n$ time units. In each time unit, you can perform one stunt. There are $k$ types of stunts, and each type has an excitement level $c_i$. If the same stunt is performed repeatedly, passengers get bored, so we define the value of performing a stunt as (time since the last time this same stunt was performed) $\times c_i$. If it is the first time performing that stunt, the value is $0$. Plan a schedule to maximize the total value.

Input Format

The first line contains two integers, $n$ and $k$, as described above. The second line contains $k$ integers, the $c_i$ values for the $k$ stunt types.

Output Format

Output a single line with one integer, the maximum total value.

5 2
2 2

12

Hint

Constraints

• For 10% of the testdata, $n \le 20$, $k \le 3$.
• For 100% of the testdata, $1 \le n \le 10^3$, $1 \le k \le 300$, $0 \le c_i \le 10^3$.

Translated by ChatGPT 5