P3918 [CTT] Stunt Flight

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.

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.

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 a single line with one integer, the maximum total value.

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