节省时间3

题目描述

童程学校的信息奥赛课非常受欢迎。每次午休，学生们都要排队找老师答疑。有的同学问题简单，答疑时间短。有的同学问题难，答疑时间长。学校看到人山人海的学生，由原来只有1位老师增加到r位老师。

现在有n位同学排队向r位老师请教，每位同学自己的答疑时间可能不同，学校想知道如何排队才能使学生总答疑完成时间最少，输出n位同学平均花费时间。

注意：答疑完成时间=自己的答疑时间+等前面同学的时间。

输入格式

第一行两个整数n和r，表示学生与老师的人数（$n \le 400$，$r \le 200$）。

第二行n个整数 $t_i$，表示每位同学自己的答疑时间（$t_i \le 20$）。

输出格式

输出n位同学平均花费时间，结果保留小数点后2位。

样例输入 #1

6 3
9 5 3 7 10 5

样例输出 #1

8.67

数据范围

$n \le 400$，$r \le 200$，$t_i \le 20$。

知识点与难度

本题涉及的知识点从属于 GESP五级（贪心基础），难度等级：⭐⭐。

测试点分布