#include <stdio.h>
#include <assert.h>
#define inf 999999999

int nb[1005], sm[1005];
int cpoint[1005][1005];
int pvalue[1005][1005];
int x[1000005];
int y[1000005];

int sum(int ini, int end)
{
    if (ini > end)
        return 0;
    return sm[end] - sm[ini-1];
}

int reducevalue(int ini, int mid, int end)
{
    return sum(ini, mid)*sum(mid+1, end);
}

int check(int ini, int end, int targ)
{
    int v, l, r;

    v = reducevalue(ini, targ  , end);//value of cutting it there
    l = reducevalue(ini, targ-1, end);//value of cutting it to the left
    r = reducevalue(ini, targ+1, end);//value of cutting it to the right

    if (v > l && v > r) return  0; //better
    if (v > l && r > v) return  1; //turn to the right :D
    if (l > v && v > r) return -1; //turn to the left :D

    assert(true);
    return 0; //it theoretically should not reach here e.e
}

int bestvalue(int bordini, int bordend)
{
    int ini, end, mid, v;
    ini = bordini;
    end = bordend;

    do
    {
        mid = (ini+end)/2;
        //bordend represents the cutspace AFTER the number (to the right)
        //we want the space right before it :p
        v = check(bordini, bordend, mid);

        if (v > 0)
            ini = mid;
        if (v < 0)
            end = mid;
    }
    while (v != 0);

    return mid;
}

int pa(int v)
{
    return ((1+v)*v)/2;
}

int gettot(int ini, int end) {
    int i, j, r = 0;

    for (i = ini; i < end; i++)
        for (j = i+1; j <= end; j++)
            r += nb[i]*nb[j];

    return r;
}

int main()
{
    int n, m;

    while (scanf (" %d %d", &n, &m) != EOF && (n || m))
    {
        int ans;
        int i, j;

        sm[0] = 0;
        for (i = 1; i <= n; i++)
        {
            scanf (" %d", &nb[i]);
            sm[i] = sm[i-1] + nb[i];
        }

        for (i = 1; i < n; i++)
            for (j = i+1; j <= n; j++)
            {
                cpoint[i][j] = bestvalue(i, j);
                pvalue[i][j] = reducevalue(i, cpoint[i][j], j);
            }

        int tsize, arrsize;
        int maxcutp, max;


        x[0] = 1;
        y[0] = n;
        max = -inf;
        tsize = arrsize = 1;
        for (i = 0, j = 0; tsize <= m; i++, j++)
        {
            if (j == tsize)
            {
                for (j = pa(tsize-1); j < pa(tsize); j++)
                {
                    if (maxcutp == j)
                    {
                        x[  arrsize  ] = x[j];
                        y[  arrsize  ] = cpoint[x[j]][y[j]];
                        x[arrsize + 1] = cpoint[x[j]][y[j]] + 1;
                        y[arrsize + 1] = y[j];
                        arrsize += 2;
                    }
                    else
                    {
                        x[arrsize] = x[j];
                        y[arrsize] = y[j];
                        arrsize++;
                    }
                }

                j = 0;
                tsize++;
                max = -inf;
            }

            if (pvalue[x[i]][y[i]] > max)
            {
                max = pvalue[x[i]][y[i]];
                maxcutp = i;
            }
        }

        ans = 0;
        for (i = pa(tsize-1); i < pa(tsize); i++) {
            ans += gettot(x[i], y[i]);
            //if (y[i] != x[i])
              //printf("DB: %d %d - %d\n", x[i], y[i], gettot(x[i], y[i]));
        }

        printf("%d\n", ans);
    }
    return 0;
}