#include <cstdio>
#include <algorithm>

using namespace std;

struct batch
{
    double le, ri;
    long long a, b;

    void dec (double lee, double rii, long long aa, long long bb)
    {
        le = lee;
        ri = rii;
        a = aa;
        b = bb;
    }
} st[100010];

long long v[100010], part[100010], sum[100010], dp[100010][16];

bool check (batch A, batch B)
{
    return (1.0 * A.a * A.le + A.b >= 1.0 * B.a * A.le + B.b);
}

int main ()
{
    freopen ("adunare.in", "r", stdin);
    freopen ("adunare.out", "w", stdout);

    int n, p;
    scanf ("%d %d", &n, &p);

    for (int i = 1; i <= n; ++i)
    {
        scanf ("%lld", &v[i]);

        part[i] = part[i - 1] + v[i];
        sum[i] = sum[i - 1] + 1LL * i * v[i];
    }

    int w = 0;
    st[++w].dec (0, 200000000000000000.0, -1LL, 0LL);

    for (int k = 1; k <= p; ++k)
    {
        if (k > 1) w = 0;
        for (int i = k; i <= n; ++i)
        {
            if (k > 1)
            {
                batch ah;
                ah.dec (0.0, 200000000000000000.0, -1LL * i, 1LL * i * part[i] - sum[i] + dp[i - 1][k - 1]);

                for (; w > 0 && check (st[w], ah); --w);

                if (w > 0) ah.le = st[w].ri = 1.0 * (ah.b - st[w].b) / (st[w].a - ah.a);
                else ah.le = 0.0;

                st[++w] = ah;
            }

            int sta = 1, dr = w, poz;
            for (; sta <= dr;)
            {
                int mij = (sta + dr) >> 1;

                if (st[mij].le <= 1.0 * part[i] && 1.0 * part[i] <= st[mij].ri)
                {
                    poz = mij;
                    break;
                }

                if (st[mij].le > 1.0 * part[i])
                    dr = mij - 1;

                else sta = mij + 1;
            }

            dp[i][k] = sum[i] + st[poz].a * part[i] + st[poz].b;
        }
    }

    printf ("%lld\n", dp[n][p]);

    return 0;
}