题目描述

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

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

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

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

输入格式

第一行，包含两个用空格分隔的正整数n、m，分别表示跑步时长、疲劳值的上限。

第二行，包含m个用空格分隔的正整数$S_{1}$,$S_{2}$,…,$S_m$，依次表示疲劳值1∼m时所分别对应的跑步速度。

输出格式

仅一行，包含一个整数，表示婷婷n分钟能够跑出的最远距离。

8 3
3 2 8

16

2 1
5

5

4 2
2 5

7

提示

婷婷先跑

3分钟，跑步距离为$3+2+8=13$，再休息3分钟将疲劳值降为0，接下来跑1分钟，距离为3，最后休息1分钟，疲劳值降为0，总距离为16。

数据范围

对于30%的数据，保证$1\le n\le 20$，$1\le m\le 10$，$1\le S_i\le 1000$。

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

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

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