题目描述

给定数组 $\textit{nums}$ 和一个整数 $k$。我们需要将数组 $\textit{nums}$ 恰好分成 $k$ 个非空的连续子数组。必须使用数组中的每一个元素，每个元素恰好属于一个子数组。

分数 定义为所有子数组的平均值的总和。

请返回能得到的最大分数。

输入格式

第一行两个正整数 $n, k$，分别表示数组 $\textit{nums}$ 的长度和必须分割成的子数组个数。

第二行 $n$ 个整数 $\textit{nums}_1, \textit{nums}_2, \dots, \textit{nums}_n$，表示数组 $\textit{nums}$ 的元素。

输出格式

输出一行一个实数，表示最大分数，保留6位小数。

样例

样例 1

样例输入 1

6 3
9 1 2 3 9 9

样例输出 1

21.750000

样例解释 1

最优分组是 $[9], [1, 2, 3, 9], [9]$。 得到的分数是 $9 + \frac{1+2+3+9}{4} + 9 = 9 + 3.75 + 9 = 21.75$。

说明/提示

• $1 \le k \le n \le 100$
• $1 \le \textit{nums}_i \le 10^4$（$1 \le i \le n$）