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:
//無心でDPします
#include <iostream>
#include <algorithm>
#include <cstdio>
#define rep(i, n) for (i = 0; i < n; i++)
#define repn(i, m, n) for (i = m; i < n; i++)
#define int long long
using namespace std;

int INF = 1e+12;
int n, m;
int a[500];
int ra[501];
double dp[501][501];	//dp[pos][cnt] = max

signed main() {
	int i, j, k;
	
	cin >> n >> m;
	rep(i, n) cin >> a[i];
	rep(i, n) ra[i + 1] = ra[i] + a[i];
	
	rep(i, n + 1) rep(j, m + 1) dp[i][j] = -INF;
	
	dp[0][0] = 0;
	rep(i, n) {
		rep(j, m) {
			repn(k, i + 1, n + 1) {
				double high = (ra[k] - ra[i]) / (double)(k - i);
				dp[k][j + 1] = max(dp[k][j + 1], dp[i][j] + high);
			}
		}
	}
	
	//rep(i, n + 1) { rep(j, m + 1) cout << dp[i][j] << " "; cout << endl; }
	printf("%.14f\n", dp[n][m]);
	return 0;
}