class Solution

{

public:

    /**

     * @param A an integer array

     * @param k an integer

     * @return an integer

     */

    int postOffice(vector<int>& A, int k)

    {

        int n = A.size();

        sort(A.begin(), A.end());

    // Cost btw. 2 houses i-j with 1 post-office - built in the mid

    vector<vector<int>> w(n + , vector<int>(n + ));

    for(int i = ; i <= n; i ++)

    {

        w[i][i] = ;

        for(int j = i + ; j <= n; j ++)

        {

        // Check both odd\even. It holds.

        w[i][j] = w[i][j-] + A[j - ] - A[(i + j) /  - ];

        }

    }

    // main DP

    vector<vector<int>> dp(n + , vector<int>(k + ));

    for(int i = ; i <= n; i++)

    {

        dp[i][] = w[][i];

    }

    for(int i = ; i <= k; i ++) // post-offices

    {

        for(int j = n; j > i; j --) // houses. Low j sets high j

        {

        dp[j][i] = INT_MAX;

        for(int x = i - ; x < j; x ++)

        {

            dp[j][i] = min(dp[j][i], dp[x][i-] + w[x + ][j]);

        }

        }

    }

    return dp[n][k];

    }

};