Problem: problem

AOR Ika got a water tank with a size of $ 1 $ in length and $ N $ in width. The aquarium is tall enough to hold water. The aquarium has $ N-1 $ partitions and is evenly spaced into $ N $ compartments. When water was poured here, the height of the water in each section became $ a_i $.

AOR Ika decided to remove some dividers and reduce the number of compartments to $ M $ or less. When you have removed the dividers, find the maximum sum of the water heights in each compartment.

The thickness of the partition can be ignored.



input

$ N \ M $
$ a_1 \ cdots a_N $

output

Output the maximum value of the total water height of each section in one line. Also, output a line break at the end. It is acceptable if the relative or absolute error is less than or equal to $ 10 ^ {-6} $.

Example

Input

5 3
9 1 2 3 9


Output

20.000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define REP(i,n) for (ll i = 0, i##_len = (n); i < i##_len; i++)
#define ALL_OF(v) (v).begin(), (v).end()

int main() {

    ll n, m; cin >> n >> m;
    vector<ll> a(n);
    REP(i, n) cin >> a[i];

    vector<ll> as(n+1, 0);
    REP(i, n) as[i+1] += as[i] + a[i];

    // dp[i][j] := 最後の仕切りが位置iにあり区画が全部でj個のときの水の高さの総和
    vector<vector<ld>> dp(n+1, vector<ld>(m+1, -1e100L));

    dp[0][0] = 0.L;

    REP(i, n) {
        REP(j, i+1) {
            REP(k, m) {
                ld x = dp[j][k] + (ld)(as[i+1] - as[j]) / (i+1 - j);
                if (dp[i+1][k+1] < x) {
                    dp[i+1][k+1] = x;
                }
            }
        }
    }

    // REP(i, n+1) REP(j, m+1) cerr << dp[i][j] << " \n"[j==m];

    cout << fixed << setprecision(30) << *max_element(ALL_OF(dp.back())) << endl;

}