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 <cstdio>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int SIZE = 510;

double dp[SIZE][SIZE];

int main(){
  int n,m;
  int a[SIZE];
  long long sum[SIZE];
  
  scanf("%d%d",&n,&m);

  sum[0] = 0;

  for(int i=0;i<n;i++){
    scanf("%d",a+i);
    sum[i+1] = a[i] + sum[i];  
  }

  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      dp[i][j] = -1e18;
    }
  }

  dp[0][0] = 0;

  double ans = 0;
  
  for(int i=0;i<m;i++){
    for(int j=0;j<=n;j++){
      for(int k=j+1;k<=n;k++){
        dp[i+1][k] = max(dp[i+1][k], dp[i][j] + (double)(sum[k] - sum[j]) / (k-j));
      }
    }
  }

  for(int i=0;i<m;i++){
    ans = max(dp[i+1][n], ans);
  }
  
  printf("%.10lf\n",ans);
  
  return 0;
}