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 JAVA):

Solution:
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		double[] arr = new double[n];
		double[] acc = new double[n + 1];
		acc[0] = 0;
		for (int i=0;i<n;i++) {
			arr[i] = sc.nextInt();
			acc[i + 1] = acc[i] + arr[i];
		}
		double [][] dp = new double[n + 1][m + 1];
		for (int i=0;i<n+1;i++) {
			for (int j=0;j<m+1;j++) {
				dp[i][j] = Integer.MIN_VALUE;
			}
		}
		dp[0][0] = 0;
		for (int i=1;i<n+1;i++) {
			for (int j=1;j<Math.min(m+1,i+1);j++) {
				for (int k=j-1;k<i;k++) {
					dp[i][j] = Math.max(dp[i][j], dp[k][j - 1] + (acc[i] - acc[k]) / (i - k));
				}
			}
		}
		System.out.printf("%.6f", dp[n][m]);
	}
}