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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

double height[501],range_height[501][501];
double dp[501][501];

int main(){

	int N,M;
	scanf("%d %d",&N,&M);

	height[0] = 0;
	for(int i = 1; i <= N; i++){
		scanf("%lf",&height[i]);
		height[i] += height[i-1];
	}

	double sum;

	for(int left = 1; left <= N; left++){
		for(int right = left; right <= N; right++){
			sum = height[right]-height[left-1];
			range_height[left][right] = sum/(double)(right-left+1);
		}
	}

	for(int right = 0; right <= N; right++){
		for(int num = 0; num <= M; num++)dp[right][num] = 0.0;
	}

	for(int right = 1; right <= N; right++){

		dp[right][1] = range_height[1][right];
		for(int left = 2; left <= right; left++){
			for(int divide_num = 2; divide_num <= min(left+1,min(right,M)); divide_num++){
				dp[right][divide_num] = max(dp[right][divide_num],dp[left-1][divide_num-1]+range_height[left][right]);
			}
		}
	}

	printf("%.10lf\n",dp[N][M]);

	return 0;
}