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>
using namespace std;

int main(){
  int n,m;
  double a[500];
  cin>>n>>m;
  for(int i=0;i<n;i++)cin>>a[i],a[i]+=(i?a[i-1]:0);
  double dp[501][501];
  for(int i=0;i<501;i++)for(int j=0;j<500;j++)dp[i][j]=-1e15;
  dp[0][0]=0;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      for(int k=0;k<=i;k++){
	dp[j+1][i+1]=max(dp[j+1][i+1],dp[j][k]+(a[i]-(k?a[k-1]:0))/(i-k+1));
      }
  printf("%.8f\n",dp[m][n]);
  return 0;
}