import std.algorithm, std.array, std.conv, std.range, std.stdio, std.string;
void main()
{
    auto buf = readln.chomp.split.to!(int[]);
    solve(buf[1], readln.chomp.split.to!(int[])).writeln;
}
long solve(int m, int[] powers)
{
    powers.sort!((a, b) => a > b);
    stderr.writefln("solve(%d, %s)", m, powers);
    int left = 0, right = 200000;
    while (left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if (handshakes(mid, powers) < m)
            right = mid;
        else
            left = mid;
    }
    assert (handshakes(left, powers) >= m);
    assert (handshakes(right, powers) < m);
    stderr.writefln("%d: %d\n%d: %d\n",
            left, handshakes(left, powers),
            right, handshakes(right, powers)
            );
    stderr.writefln("%d: %d\n%d: %d\n",
            left, happiness(left, powers),
            right, happiness(right, powers)
            );
    return happiness(right, powers) + (m - handshakes(right, powers)) * left;
}
/// count the number of handshakes with t <= happiness
long handshakes(int t, int[] powers)
{
    long ret;
    foreach (i, p; powers)
    {
        if (powers[i] + powers[0] < t)
            continue;
        if (t <= powers[i] + powers[powers.length - 1])
        {
            ret += powers.length;
            continue;
        }
        size_t leftGeq = 0, rightLess = powers.length - 1;
        while (leftGeq + 1 < rightLess)
        {
            immutable mid = leftGeq + (rightLess - leftGeq) / 2;
            if (powers[i] + powers[mid] < t)
                rightLess = mid;
            else
                leftGeq = mid;
        }
        ret += leftGeq + 1;
    }
    return ret;
}
unittest
{
    assert (handshakes(11, [8, 7, 7, 6]) == 16);
    assert (handshakes(12, [8, 7, 7, 6]) == 16);
    assert (handshakes(13, [8, 7, 7, 6]) == 15);
    assert (handshakes(14, [8, 7, 7, 6]) == 11);
    assert (handshakes(15, [8, 7, 7, 6]) ==  5);
    assert (handshakes(16, [8, 7, 7, 6]) ==  1);
    assert (handshakes(17, [8, 7, 7, 6]) ==  0);
}

/// total happiness of handshakes with t <= happiness
long happiness(int t, int[] powers)
{
    auto cumPowers = powers.cumulativeFold!((a, b) => (a + b))(long(0)).array;
    long ret;
    foreach (i, p; powers)
    {
        if (powers[i] + powers[0] < t)
            continue;
        if (t <= powers[i] + powers[powers.length - 1])
        {
            ret += cumPowers[powers.length - 1] + powers[i] * powers.length;
            continue;
        }
        size_t leftGeq = 0, rightLess = powers.length - 1;
        while (leftGeq + 1 < rightLess)
        {
            immutable mid = leftGeq + (rightLess - leftGeq) / 2;
            if (powers[i] + powers[mid] < t)
                rightLess = mid;
            else
                leftGeq = mid;
        }
        ret += cumPowers[leftGeq] + powers[i] * (leftGeq + 1);
    }
    return ret;
}
unittest
{
    assert (happiness(11, [8, 7, 7, 6]) == 224);
    assert (happiness(12, [8, 7, 7, 6]) == 224);
    assert (happiness(13, [8, 7, 7, 6]) == 212);
    assert (happiness(14, [8, 7, 7, 6]) == 160);
    assert (happiness(15, [8, 7, 7, 6]) ==  76);
    assert (happiness(16, [8, 7, 7, 6]) ==  16);
    assert (happiness(17, [8, 7, 7, 6]) ==   0);
}
unittest
{
    assert (solve(3, [10, 14, 19, 34, 33]) == 202);
    assert (solve(14, [1, 3, 5, 110, 24, 21, 34, 5, 3]) == 1837);
    assert (solve(73, [67597, 52981, 5828, 66249, 75177, 64141, 40773, 79105, 16076]) == 8128170);
}
unittest
{
    stderr.writeln("unittest passed!");
}
