g6-07903. 学习小组 未做

有 $n$ 个人排成一排，要分成若干连续小组。每组人数 $k$ 必须是 $1\sim K$ 之一；人数为 $k$ 的小组贡献 $a_k$ 分。求最大总得分。

第一行两个整数 $n,K$。

第二行 $K$ 个正整数 $a_1,\dots ,a_K$。

一行一个整数，表示最大总得分。

输入 1

5 2
3 5

输出 1

15

对于所有数据，$1\le n\le 100000$，$1\le K\le 100$，$1\le a_k\le 10000$。