#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

const int oo_min=0xc0c0c0c0,oo_max=0x3f3f3f3f;

namespace dts
{
    int n,m;
    int a[1000+1+1];
    int sum[1000+1+1];
    int c[1000+1+1][1000+1+1];
    int f[1000+1+1][1000+1+1];
    int s[1000+1+1][1000+1+1];
    void pr_dp()
    {
        memset(sum,0,sizeof(sum));
        for (int i=1;i<=n;i++)
            sum[i]=sum[i-1]+a[i];
        memset(c,0,sizeof(c));
        for (int i=1;i<=n;i++)
            for (int j=i;j<=n;j++)
                c[i][j]=c[i][j-1]+(a[j]*(sum[j-1]-sum[i-1]));
        memset(f,oo_max,sizeof(f));
        memset(s,0,sizeof(s));
        for (int i=0;i<=n;i++)
        {
            s[i][0]=0;
            s[n+1][i]=n;
            f[i][0]=c[1][i];
        }
    }
    int pro_dp()
    {
        for (int i=1;i<=m;i++)
            for (int j=n;j>=1;j--)
                for (int k=s[j][i-1];k<=s[j+1][i];k++)
                    if (f[k][i-1]+c[k+1][j]<f[j][i])
                    {
                        s[j][i]=k;
                        f[j][i]=f[k][i-1]+c[k+1][j];
                    }
        return f[n][m];
    }
    void main()
    {
        while (~scanf("%d%d",&n,&m))
            if (n>0&&m>0)
            {
                for (int i=1;i<=n;i++)
                    scanf("%d",&a[i]);
                pr_dp();
                printf("%d\n",pro_dp());
            }
            else
                break;
    }
};

int main()
{
    dts::main();
}