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:
#ifndef VS
#include<bits/stdc++.h>
#endif

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};


constexpr double INF = 1e18;
int main() {
	int N,M;
	cin >> N >> M;
	vector<double> a(N);
	cin >> a;
	vector<vector<double>> dp(N + 1, vector<double>(M + 1, -INF));
	dp[0][0] = 0;
	for (int i : range(N + 1)) {
		for(int c:range(M)){
			double hsum = 0;
			double len = 0;
			for (int j : range(i + 1, N + 1)) {
				hsum += a[j - 1];
				len += 1.0;
				chmax(dp[j][c + 1], dp[i][c] + hsum / len);
			}
		}
	}
	cout << fixed;
	cout << setprecision(10);
	double ret = -INF;
	for (int i : range(M + 1))chmax(ret, dp.back()[i]);
	cout << ret << endl;
	return 0;
}