题目描述

皮皮有每天晨跑的好习惯。他每次跑步的时长都恰好为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

提示

对于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$。

皮皮先跑

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

8 3
3 2 8

16

8 3 
3 2 8

16

8 3  
3 2 8

16