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"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

const LL inf = 11234567890123456;
LL N, M;
std::vector<LL>a;
long double memo[512][512];

long double dp(LL p, LL c)
{
	if (p == N + 1)
	{
		if (c > M) return -inf;
		return 0;
	}
	if (memo[p][c] != -1.) return memo[p][c];
	long double res = -inf;
	for (LL w = 1; w <= N; ++w)
	{
		if (p + w - 1 >= N + 1) break;
		res = std::max(res, dp(p + w, c + 1) + (a[p + w - 1] - a[p - 1]) / (long double)w);
	}
	return memo[p][c] = res;
}

int main()
{
	in >> N >> M;
	a.resize(N + 1);
	rep(i, N) in >> a[i + 1];
	rep(i, N) a[i + 1] += a[i];
	rep(i, 512) rep(j, 512) memo[i][j] = -1.;
	out << std::fixed << std::setprecision(6);
	out << dp(1, 0) << std::endl;
	return 0;
}