皮皮有每天晨跑的好习惯。他每次跑步的时长都恰好为 $n$ 分钟。在这 $n$ 分钟的跑步前，皮皮的疲劳值初始为 $0$。

在任一分钟内，皮皮可以选择跑步，也可以考虑休息。每跑一分钟，皮皮的疲劳值就会增加 $1$，而每休息一分钟，皮皮的疲劳值则减 $1$（如果这一分钟休息前的疲劳值为 $0$，则休息后仍旧为 $0$）。但是，每当皮皮休息时，他会一直休息到疲劳值为 $0$ 时，才会考虑继续跑步。当然，为了身体健康，皮皮决不能让自己的疲劳值超过 $m$。

显然，皮皮每分钟的跑步速度不可能完全相同。如果这一分钟跑步会让疲劳值增加至 $i$，则皮皮在这一分钟的跑步速度就是 $S_i$。

皮皮希望在 $n$ 分钟的跑步结束时，疲劳值恰好为 $0$，但又能在这 $n$ 分钟内跑出尽可能远的距离。你能帮他计算，他能够跑出最远的距离是多少吗？

对于 $30\%$ 的数据，保证 $1≤n≤20,\ 1≤m≤8,\ 1≤S_i≤1000$。

另有 $20\%$ 的数据，保证 $m = 1$。

另有 $10\%$ 的数据，保证 $S_i$ 单调递减。

对于100%的数据，保证 $1≤n≤10000,\ 1≤m≤500,\ 1≤S_i≤1000$。