/*
Author: Yiu Yu Ho

Let f(x,k) be the minimum value achieved splitting depots [0, x] with k attacks.
f(x,k) = min(f(y,k-1)+g(y+1,x), y = 0..x-1), where g(i,j) is the strategic 
score for depots [i,j] inclusive.

This is a simple DP problem, the only trick required is to pre-compute g.
*/

import java.util.*;
import java.io.*;

public class lawrence 
{
	public static Scanner in = new Scanner(System.in);
	public static PrintStream out = System.out;

	public final int oo = 987654321;

	public void main() 
	{
		int n,m;
		int[] cost;
		int[][] w,sum;
		int[] v;
		int i,j,k,x,y;

		n = in.nextInt();
		while(n>0)
		{
			m = in.nextInt();
			
			v=new int[n];
			for(i=0;i<n;++i) v[i]=in.nextInt();

			sum=new int[n][n];
			for(i=0;i<n;++i)
			{
				sum[i][i]=v[i];
				for(j=i+1;j<n;++j) sum[i][j] = sum[i][j-1] + v[j];
			}

			w = new int[n][n];
			for(i=0;i<n;++i)
			{
				w[i][i] = 0;
				for(j=i+1;j<n;++j) w[i][j] = w[i][j-1] + v[j]*sum[i][j-1];
			}

			cost = new int[n];
			//k = 0;
			for(i=0;i<n;++i) cost[i] = w[0][i];

			for(k=1;k<=m;++k)
			{
				for(i=n-1;i>=0;--i)
				{
					for(x=i-1;x>=0;--x)
					{
						if(w[x+1][i]>=cost[i]) break;
						cost[i]=Math.min(cost[i],cost[x]+w[x+1][i]);
					}
				}
			}

			out.println(cost[n-1]);

			n=in.nextInt();
		}//end while n>0

	}

	public static void main(String[] args)
	{
		long startTime = System.currentTimeMillis();
		(new lawrence()).main();
		System.err.println("Time = "+(System.currentTimeMillis() - startTime)+"(ms)");
	}
}