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 N,M;
double dp[600][600];
double a[600];
double b[600];

const double INF = 1e20;

double Sum(int l,int r){
  if(l==0)return b[r-1];
  return b[r-1]-b[l-1];
}

int main(){

  cin>>N>>M;
  for(int i=0;i<N;i++){
    cin>>a[i];
    b[i]=a[i];
    if(i>0)b[i]+=b[i-1];
  }


  for(int i=0;i<600;i++)
    for(int j=0;j<600;j++)
      dp[i][j]=-INF;
  dp[0][0]=0;

  double maxm=0.0;
  
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      for(int k=i-1;k>=0;k--){
        dp[i][j]=max(dp[i][j], dp[k][j-1] + ( Sum(k,i) / (i-k) ) );
        if(i==N)maxm=max(maxm, dp[i][j]);
      }

      //      cout<<dp[i][j]<<' ';
    }
    //    cout<<endl;
  }

  
  printf("%.10f\n",maxm);
  return 0;
}