import java.io.*;
import java.util.*;
import static java.lang.Math.*;

// This is a simple 2D dynamic programming problem, 
// with the number of attacks being one dimension, 
// and the depots being the other. The trick is to
// precompute the costs of leaving the rail line intact
// between every pair of depots.
public class lawrence_judge
{
    private Scanner sc;
    private PrintStream ps;

    public String toString()
    {
        return "lawrence_judge";
    }

    // memo[i][j] is the best result you can achieve with i attacks, 
    // starting at depot j and going to the end of the line.
    private int memo[][];

    // cost[i][j] (i<=j) is the cost of leaving the railroad intact
    // from depot i through depot j (inclusive)
    private int cost[][];

    // n = number of depots, m = number of attacks
    private int n, m;

    // Figure out the best way to use "attacks" attacks, 
    // starting at depot "start" and going to the end of the line.
    private int place( int attacks, int start )
    {
        // If this has already been computed, then don't recompute it.
        // -1 is a flag that it hasn't been computed.
        if( memo[attacks][start]<0 )
        {
            if( attacks==0 )
            {
                // If there are no more attacks available, then it's
                // just the cost of leaving the rail line intact from 
                // here to the end.
                memo[attacks][start] = cost[start][n-1];
            }
            else
            {
                // If there are attacks left, find the best place for the
                // next attack.
                int best = Integer.MAX_VALUE;

                // Go through all the possible places Lawrence could use this attack.
                // We'll see what happens when Lawrence attacks between depots i and i+1.
                // Start at the start - but be sure to leave Lawrence enough room at
                // the end to use all of his remaining attacks!
                for( int i=start; i<n-attacks; i++ )
                {
                    // The cost of making the next attack just after i is the cost of
                    // leaving the rail line from depot "start" to depot "i" intact, 
                    // plus the cost of making the remaining attacks from depot i+1 
                    // to the end of the line.
                    int here = cost[start][i] + place( attacks-1, i+1 );
                    if( here<best ) best = here;
                }

                // Remember the best
                memo[attacks][start] = best;
            }
        }

        return memo[attacks][start];
    }

    public void doit() throws Exception
    {
        sc = new Scanner( System.in );
        ps = System.out;

        for(;;)
        {
            // Read n & m, break at end
            n = sc.nextInt();
            m = sc.nextInt();
            if( n==0 && m==0 ) break;

            // Read the stations
            int stations[] = new int[n];
            for( int i=0; i<n; i++ )
            {
                stations[i] = sc.nextInt();
            }

            // Precompute the cost of leaving stations connected
            // sum[a][b] (a<=b) is the sum of strategic values of depots a through b
            // cost[a][b] (a<=b) is the cost of leaving the railroad connected from depot a through depot b
            int sum[][] = new int[n][n];
            cost = new int[n][n];
            for( int j=0; j<n; j++ )
            {
                sum[j][j] = stations[j];
                cost[j][j] = 0;
                for( int i=0; i<j; i++ )
                {
                    sum[i][j] = sum[i][j-1] + stations[j];
                    cost[i][j] = cost[i][j-1] + stations[j]*sum[i][j-1];
                }
            }

            // Stuff memo[][] with -1's
            memo = new int[m+1][n];
            for( int i=0; i<=m; i++ )
            {
                Arrays.fill( memo[i], -1 );
            }

            // Just let the recursion do the work
            ps.println( place( m, 0 ) );
        }
    }

    public static void main( String args[] ) throws Exception
    {
        new lawrence_judge().doit();
    }
};