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:
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

double DP[550][550] = {};

int main(){
	
	int N, M;
	cin >> N >> M;
	
	long long int a[1000];
	for(int i = 0; i < N; i++){
		cin >> a[i];
	}
	
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= M; j++){
			DP[i][j] = -INF;
		}
	}
	DP[0][0] = 0;
	
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			long long int S = 0;
			for(int k = 1; k <= i; k++){
				S += a[i - k];
				DP[i][j] = max(DP[i][j], DP[i - k][j - 1] + S / (double)k);
			}
		}
	}
	
	printf("%.10f\n", DP[N][M]);
	
	return 0;
}