#include using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() #define CLR(t,v) memset(t,(v),sizeof(t)) templateostream& operator<<(ostream& os,const pair&a){return os<<"("<void chmin(T&a,const T&b){if(a>b)a=b;} templatevoid chmax(T&a,const T&b){if(avoid pv(T a,T b){for(T i=a;i!=b;++i)cerr<<(*i)<<" ";cerr<void pv(T a,T b){} #endif ll nextLong() { ll x; scanf("%lld", &x); return x;} const ll INF = 1LL << 61; const int MAX_N = 305; ll A[MAX_N]; ll dp[MAX_N][MAX_N][2][MAX_N]; ll ans[MAX_N]; int main2() { int N = nextLong(); int K = nextLong(); REP(i, N) A[i] = nextLong(); REP(i, N) ans[i] = -INF; REP(L, MAX_N) REP(R, MAX_N) REP(side, 2) REP(k, MAX_N) dp[L][R][side][k] = -INF; REP(i, N) { dp[i][i][0][K] = K * A[i]; dp[i][i][1][K] = K * A[i]; } for (int k = K; k >= 0; k--) { REP(L, N) for (int R = L; R < N; R++) REP(side, 2) { const ll val = dp[L][R][side][k]; if (val < -INF / 2) continue; const int D = R - L; if (side == 0 && L - 1 >= 0 && k-1 >= 0) { chmax(dp[L-1][R][side][k-1], val + (k-1) * A[L-1]); } if (side == 1 && R + 1 <= N-1 && k-1 >= 0) { chmax(dp[L][R+1][side][k-1], val + (k-1) * A[R+1]); } if (D >= 1 && k - D >= 0) { chmax(dp[L][R][1-side][k-D], val); } if (D >= 1 && k - 2 >= 0) { chmax(dp[L][R][side][k-2], val); } } } for (int k = 0; k < K; k++) REP(L, N) for (int R = L; R < N; R++) REP(side, 2) { const ll val = dp[L][R][side][k]; if (val < -INF / 2) continue; if (side == 0) { for (int i = L + (k & 1); i-L <= k && i <= R; i += 2) { chmax(ans[i], val); } } else if (side == 1) { for (int i = R - (k & 1); R-i <= k && i >= L; i -= 2) { chmax(ans[i], val); } } } REP(i, N) cout << ans[i] << endl; return 0; } int main() { #ifdef LOCAL for (;!cin.eof();cin>>ws) #endif main2(); return 0; }