#include <cstdio> #include <cstring> #include <iostream> #include <vector> #include <algorithm> using namespace std; #define INF 1200000000 const int maxn = 102; const int maxm = 31; const int M = 40000; int d[maxm][maxn],n,m,p[maxn]; bool vis[maxm][maxn]; /* 3 3 3 6 7 240013 *** 当3守卫1,剩下问题的最优解为 6 13并不构成原问题的最优解所以 (以守卫最薄弱尽量大的情况下,值最小来定义状态,并不可解) 3 13 */ int dp(int i,int j){ if(vis[i][j]) return d[i][j]; vis[i][j]=true; if(i==m){ if(j==n) return d[i][j]=INF; return d[i][j]=0; } int lim=min(n,p[i+1]+j); for(int k=j;k<=n;k++){ int num; if(k==j) num=dp(i+1,k); else num=min(dp(i+1,k),p[i+1]/(k-j)); if(k==j) d[i][j]=num; else d[i][j]=max(d[i][j],num); } return d[i][j]; } int best; int mincost(int i,int j){ if(vis[i][j]) return d[i][j]; vis[i][j]=true; if(i==m){ if(j==n) return d[i][j]=0; return d[i][j]=INF; } int& ans=d[i][j]; ans=INF; for(int k=j;k<=n;k++){ int num; if(k==j) num=mincost(i+1,k); else { if(p[i+1]/(k-j)<best) break; num=mincost(i+1,k)+p[i+1]; } ans=min(ans,num); } return ans; } int main() { while(scanf("%d %d",&n,&m)==2){ if(!n&&!m) break; for(int i=1;i<=m;i++) scanf("%d",&p[i]); memset(vis,false,sizeof(vis)); best = dp(0,0); printf("%d ",best); memset(vis,false,sizeof(vis)); printf("%d\n",best==0 ? 0:mincost(0,0)); } return 0; }