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

/**
 * Estimation
 * @author vanb
 *
 * There are two parts to this algorithm. First, we've got to
 * compute costs[i][j], which is the error if we group together
 * A[i]..A[j]. Then, we've got to do some DP to find the best
 * partitioning. 
 * 
 * Fun Fact: For any group of numbers A[i]..A[j], the value C
 * which minimizes the error SUM{|A[k]-C|} for i<=k<=j is the median of A[i]..A[j].
 * It's true - but it's left as an exercise for the reader to prove it.
 * 
 * We'll compute the matrix of costs by using a binary tree to keep track
 * of the median. For efficiency, we'll use AVL balancing. Once we compute costs[i][j],
 * we'll do a DP to find the best partitioning. The DP will look like this:
 * 
 * Let best[i][k] be the best you can do splitting A[0]..A[i] into k partitions.
 * Then best[i][k] = MIN{best[j][k-1] + costs[j+1][i]} for j<i
 * So then, best[n-1][p] is our answer.
 */
public class estimate
{
    public Scanner sc;
    public PrintStream ps;
    
    public static final int LARGE = 1000000000;
    
    /**
     * Node of a balanced AVL binary tree, and a double linked sorted list.
     * 
     * @author vanb
     */
    public class Node
    {
        // Value in the node, height of this subtree
        public int value, height;
        
        // Links to left child, right child and parent,
        // along with previous and next nodes of a linked linear list.
        public Node left, right, parent, prev, next; 
        
        /**
         * Create a new unlinked node.
         * 
         * @param v Value for this node.
         */
        public Node( int v )
        {
            value = v;
            height = 0;
            left = right = parent = prev = next = null;
        }

        /**
         * Height of the left subtree
         * 
         * @return Height of the left subtree
         */
        public int leftheight()
        {
            return left==null ? 0 : left.height;
        }
        
        /**
         * Height of the right subtree 
         * 
         * @return Height of the right subtree
         */
        public int rightheight()
        {
            return right==null ? 0 : right.height;
        }
                   
        /**
         * Recalculate the height of this node
         */
        public void recalc()
        {
            height = 1 + Math.max( leftheight(), rightheight() );
        }
        
        /**
         * Perform an AVL tree rotate left on this node.
         */
        public void rotateleft()
        {
            Node p = parent;
            Node pivot = right;
            Node subtree = pivot.left;
            
            right = subtree;
            if( subtree!=null ) subtree.parent = this;
            
            parent = pivot;
            pivot.left = this;
            
            if( p==null )
            {
                root = pivot;   
            }
            else if( p.left == this )
            {
                p.left = pivot;
            }
            else
            {
                p.right = pivot;   
            }
            pivot.parent = p;
            
            recalc();
            pivot.recalc();
            if( p!=null ) p.recalc();
        }
        
        /**
         * Perform an AVL tree rotate right on this node.
         */
        public void rotateright()
        {
            Node p = parent;
            Node pivot = left;
            Node subtree = pivot.right;
            
            left = subtree;
            if( subtree!=null ) subtree.parent = this;
            
            parent = pivot;
            pivot.right = this;
            
            if( p==null )
            {
                root = pivot;   
            }
            else if( p.left == this )
            {
                p.left = pivot;
            }
            else
            {
                p.right = pivot;   
            }
            pivot.parent = p;
            
            recalc();
            pivot.recalc();
            if( p!=null ) p.recalc();
        }

        /**
         * Insert a node into the subtree rooted here.
         * 
         * @param node Node to insert
         */
        public void insert( Node node )
        {
            if( node.value <= value )
            {
                // If this node has no left subtree, then insert here.
                if( left==null )
                {
                    left = node;
                    node.parent = this;
                    
                    // If we're inserting the new node to the left of this node,
                    // then the new value is immediately previous
                    // to this node in the sorted linked list.
                    Node prevnode = prev;
                    node.next = this;
                    node.prev = prevnode;
                    prev = node;
                    if( prevnode!=null ) prevnode.next = node;                   
                }
                else
                {
                    left.insert( node );
                }
            }
            else
            {
                // If this node has no right subtree, then insert here.
                if( right==null )
                {
                    right = node;
                    node.parent = this;
                    
                    // If we're inserting the new node to the right of this node,
                    // then the new value is immediately following
                    // this node in the sorted linked list.
                    Node nextnode = next;
                    node.prev = this;
                    node.next = nextnode;
                    next = node;
                    if( nextnode!=null ) nextnode.prev = node;                   
                }
                else
                {
                    right.insert( node );
                }
            }
            
            recalc();
            
            // Perform AVL balancing
            if( leftheight()-rightheight()>1 )
            {
                if( left.rightheight()>left.leftheight() )
                {
                    left.rotateleft(); 
                }
                rotateright();
            }
            else if( rightheight()-leftheight()>1 )
            {
                if( right.leftheight()>right.rightheight() )
                {
                    right.rotateright();
                }
                rotateleft();   
            }
        }       
    }    
    
    public Node root;
   
    /**
     * Do it!
     * @throws Exception
     */
    public void doit() throws Exception
    {
        sc = new Scanner( System.in ); //new File( "estimate.in" ) );
        ps = System.out; //new PrintStream( new FileOutputStream( "estimate.out" ) );
        
        // Allocate everything beforehand
        int costs[][] = new int[2000][2000];
        int best[][] = new int[2000][2000];
        int a[] = new int[2000];
        
        for(;;)
        {
            int n = sc.nextInt();
            int p = sc.nextInt();
            if( n==0 ) break;
            
            for( int i=0; i<n; i++ )
            {
                a[i] = sc.nextInt();
            }
            
            for( int i=0; i<n; i++ )
            {
                // Start afresh for each i
                root = new Node( a[i] );
                Node median = root;
                
                // 'lo' is the number of values less than the current median,
                // 'hi' is the number of values greater than the current median,
                int lo = 0, hi = 0;
                
                // We'll keep a running tally of the cost
                int cost = 0;
                
                // Fill in the ith row of the costs[][] table
                Arrays.fill( costs[i], 0 );
                for( int j=i+1; j<n; j++ )
                {
                    // Insert this new value into the tree
                    Node node = new Node( a[j] );
                    root.insert( node );
                    if( node.value<=median.value ) ++lo; else ++hi;
                    
                    // Do we need to find a new median?
                    if( lo>hi+1 ) 
                    {
                        // Too many values are less than our current median.
                        // We need to move it back by 1 value.
                        int old = median.value;
                        median = median.prev;
                        --lo; ++hi;
                        
                        // This is the change in cost we incur by changing the median
                        cost += (hi-lo)*(old-median.value);
                    }
                    else if( hi>lo+1 ) 
                    {
                        // Too many values are greater than our current median.
                        // We need to move it up by 1 value.
                        int old = median.value;
                        median = median.next;
                        ++lo; --hi;
                        
                        // This is the change in cost we incur by changing the median
                        cost += (lo-hi)*(median.value-old);
                    }
                    
                    // This is the change in cost we incur by adding this new value.
                    cost += Math.abs( median.value - node.value );
                    
                    // Remember it!
                    costs[i][j] = cost;
                }
            } 
                       
            // Now, the DP.
            // best[i][k] will be the best you can do
            // splitting a[0]..a[i] into k partitions.
            for( int i=0; i<n; i++ )
            {
                // 0 partitions - not possible
                best[i][0] = LARGE;
                
                // 1 partition - just put all of 0..i together
                best[i][1] = costs[0][i];
                
                // Now, go from 2 partitions to p partitions
                for( int k=2; k<=p; k++ )
                {
                    best[i][k] = LARGE;
                    
                    // Find the best place to split, where the error
                    // of splitting 0..j into k-1 partitions, plus the
                    // cost of partition j+1..i, is smallest.
                    for( int j=0; j<i; j++ )
                    {
                        int cost = best[j][k-1] + costs[j+1][i];
                        if( cost<best[i][k] ) best[i][k] = cost;
                    }
                }
            } 
            
            ps.println( best[n-1][p] );
        }
    }
        
    /**
     * Main
     * @param args unused
     * @throws Exception
     */
    public static void main( String[] args ) throws Exception
    {
        new estimate().doit();
    }
}