#include<bits/stdc++.h>

using namespace std;

int n,m,a[],f[][],mi[][],i,j;

int main()

{

    cin>>n>>m;

    for(i=;i<=n;i++)cin>>a[i];

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

        for(j=;j<=m;j++)

            f[i][j]=;//赋为最大值

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

    {

        for(j=i+;j<=n;j++) mi[i][j]=mi[i][j-]+a[j]-a[(i+j)/];//从第i个村庄到第j个村庄中只建一个邮局的总路径长度

        f[i][]=mi[][i];//转移到f

    }

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

        for(j=;j<=m;j++)

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

                f[i][j]=min(f[i][j],f[k][j-]+mi[k+][i]);

    cout<<f[n][m]<<endl;

    return ;

}

#include<iostream>

#include<cstring>

using namespace std;

const int N = ;

int a[N],f[N];

int main()

{

    int n;

    cin>>n;

    for(int i=;i<n;i++)cin>>a[i];

    for(int i=;i<n;i++)f[i]=;

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

    {

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

        {

            if(a[j]<a[i])f[i]=max(f[i],f[j]+);

        }

    }

    int ans = ;

    for(int i=;i<n;i++)ans = max(ans,f[i]);

    cout<<ans<<endl;

    return ;

}

/*

   1. 这题不支持Special Judge...so设置状态转移方程的时候 要设置成LCIS是以第一个数组的第j个元素结尾的 而不能是第二个数组 - - 就是这么坑0-0

   2. 记录LCIS中的元素并输出 dp的时候对结构体dp  结构体中vector记录LCIS中元素。

 */

#include<iostream>

#include<vector>

using namespace std;

struct Node

{

    int val = ;

    vector<int>v;

};  

int main() {

    int a[], b[];

    Node dp[];

    int m, n;

    cin >> m;

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

        cin >> a[i];

    cin >> n;

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

        cin >> b[i];

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

    {

        Node Max;

        for (int j = ; j <= m; j++) {

            if (b[i] > a[j] && dp[j].val > Max.val)

                Max = dp[j];

            if (b[i] == a[j]) {

                dp[j].val = Max.val + ;

                dp[j].v = Max.v;

                dp[j].v.push_back(b[i]);

            }

        }

    }

    Node Max = dp[];

    for (int i = ; i <= m; i++) {

        if (dp[i].val > Max.val)

            Max = dp[i];

    }

    cout << Max.val << endl;

    for (int i = ; i < Max.v.size(); i++)

        cout << Max.v[i] << " ";

    cout << endl;

    return ;

}  

#include<iostream>

#include<cstring>

using namespace std;

int main()

{

    int n,t;

    int f[],a[];

    cin>>n>>t;

    for(int i=;i<=n;i++)cin>>a[i];

    f[]=;

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

        for(int j=t;j>=a[i];j--)

            f[j]+=f[j-a[i]];

    cout<<f[t]<<endl;

    return ;

}