You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

众所周知，西西艾弗岛上的机器人喜欢吃苹果。

题目描述

据饲养员小 P 介绍：

• 机器人一天最多可以吃 $m$ 个苹果。
• 一天内通过吃苹果获得的快乐值具体为：$A_0, A_1, \cdots, A_m$；如果某一天饲养员共投喂机器人 $i$ 个苹果，则这一天机器人获得的快乐值为 $A_i$。
• 特别地 $A_0 = 0$，快乐值并不会凭空产生。

现在小 P 有 $n$ 个苹果，试帮助小 P 计算：向机器人投喂这 $n$ 个苹果能获得的最大快乐值收益。

输入格式

从标准输入读入数据。

输入共两行。

第一行包含两个整数 $n$ 和 $m$，分别表示苹果总数和每天最大投喂量。

第二行依次包含 $m$ 个整数 $A_1, A_2, \cdots, A_m$，表示一天内投喂不同苹果数的收益。

输出格式

输出到标准输出。

输出仅一个整数，表示投喂全部 $n$ 个苹果能获得的最大收益。

10 5
1 3 5 3 1

16

样例 1 解释

一种最优投喂方案为：投喂四天，每天分别投喂 $3,3,1,3$ 个苹果。

如该样例所示，收益序列 $A$ 不一定单调递增，即一天内吃较多苹果可能反而获得较小快乐值。

4 3
1 60 100

120

样例 2 解释

一种最优投喂方案为：投喂两天，每天投喂 $2$ 个苹果。

子任务

$40\%$ 的测试数据保证：$n \le 50,~m = 5$；

另有 $40\%$ 的测试数据保证：$n = 60,~m = 6$；

全部测试数据保证：$0<n\le 10^4,~0<m\le 100,~0\le A_i\le 10^5$。