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;

using int64 = long long;

int main() {
  int N, M, A[500];
  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }

  vector< double > dp(N + 1, -1e9);
  dp[0] = 0;
  for(int i = 0; i < M; i++) {
    vector< double > dp2(dp);
    for(int j = 0; j < N; j++) {
      int64 sum = 0;
      for(int k = j; k < N; k++) {
        sum += A[k];
        dp2[k + 1] = max(dp2[k + 1], dp[j] + 1.0 * sum / (k - j + 1));
      }
    }
    dp.swap(dp2);
  }
  cout << fixed << setprecision(10) << dp.back() << endl;
}