#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 10005;
int dp[MAXN][30];
int n, k, a[30];
int main(){
cin >> n >> k;
for(int i=1; i<=k; i++) cin >> a[i];
memset(dp, 0x3f, sizeof(dp));
for(int i=0; i<=k+1; i++) dp[0][i] = 0;
for(int i=k; i; i--) dp[1][i] = min(a[i], dp[1][i+1]);
dp[1][0] = 0;
for(int i=1; i<=n; i++){
for(int j=k; j; j--){
for(int l=0; l<=i; l++){
dp[i][j] = min(dp[i][j], dp[i-l][j+1] + dp[l][0] + l * a[j]);
}
}
for(int j=1; j<i; j++){
for(int l=1; l<=k; l++){
dp[i][0] = min(dp[i][0], dp[j][0] + dp[i-j][l + 1] + j * a[l]);
}
}
}
cout << dp[n][0] << endl;
}
