#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;

//"Infinity" value
#define INF 1000000000

//totalCost[M][N] is the total cost of an unbroken chain of depots from M to N.
int totalCost[500][500];
//Memoized results of the recurse() function
int memo[500][500];

/* Recursive (with memoization) function to calculate the minimum strategic value 
of all the depots from 0 to "lastDepot", given the number of attacks we have left. */
int recurse(int lastDepot, int attacks)
{
    //Depot 0 is by itself, so it costs nothing   
    if (lastDepot == 0)
       return 0;
    
    //No more attacks, so the rest of the depots stay connected
    if (attacks == 0)
       return totalCost[0][lastDepot];
       
    //If we've already processed this input, return the memoized result
    if (memo[lastDepot][attacks] >= 0)
       return memo[lastDepot][attacks];
       
    int minCost = INF;
       
    //For each depot I from 0 to lastDepot-1, try attacking the rail between depots I and I+1
    for (int i = 0; i < lastDepot; i++)
    {
        int cost = totalCost[i+1][lastDepot] + recurse(i, attacks-1);
        if (cost < minCost)
           minCost = cost;
    }
    memo[lastDepot][attacks] = minCost;
    return minCost;
}

int main()
{
    ifstream infile("lawrence.in");
    ofstream outfile("lawrence.out");
    
    while (true)
    {
          //Reset data structures
          for (int i = 0; i < 500; i++)
          for (int j = 0; j < 500; j++)
              memo[i][j] = -1;
          
          //Input the number of depots and attacks
          int numDepots, numAttacks;
          infile >> numDepots >> numAttacks;
          if (numDepots == 0)
             return 0;
             
          //Input the strategic values
          int stratValue[500];
          int stratValueSum[500];
          for (int i = 0; i < numDepots; i++)
              infile >> stratValue[i];
          
          //Calculate the sums of strategic values (this will help with cost calculations)
          stratValueSum[0] = stratValue[0];
          for (int i = 1; i < numDepots; i++)
              stratValueSum[i] = stratValue[i] + stratValueSum[i-1];
              
          //Calculate the total cost of each possible unbroken chain of depots
          for (int i = 0; i < numDepots; i++)
          {
              totalCost[i][i] = 0;
              
              /* Cost of a chain from depot I to J = (cost from I to J-1) + 
              (J's strategic value) * (sum of strategic values from I to J-1) */
              for (int j = i+1; j < numDepots; j++)
              {
                  totalCost[i][j] = totalCost[i][j-1]
                                  + stratValue[j] * (stratValueSum[j-1] - stratValueSum[i-1]);
              }
          }                
          //Find the minimum strategic value and output it!
          outfile << recurse(numDepots-1, numAttacks) << endl;
    }
    return 0;
}