[ABC355] G - Baseball

G - Baseball

Time Limit: 5 sec / Memory Limit: 1024 MB

分数：650分

题面

你有一个长度为的序列。高桥和青木将使用序列进行一场游戏。

首先，高桥将从中选择个不同的整数。

接着，青木将以与成比例的概率从中选择一个整数。即，选择整数的概率为。然后，青木的分数将是。

高桥希望最小化青木分数的期望值。找到当高桥选择以使得该值最小化时，青木分数的期望值，再乘以。保证最终输出的值为整数。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入中以以下格式给出：

输出

输出答案。

---

输入样例 1

5 2
1 1 1 1 1

输出样例 1

3

青木选择的概率都相等：。

如果高桥选择和，那么青木分数的期望值将为。

如果高桥选择和，那么青木分数的期望值将为。

无论高桥如何选择，青木分数的期望值都不会小于。因此，最小值为，输出该值乘以，即。

---

输入样例 2

5 1
0 0 1 0 0

输出样例 2

0

---

输入样例 3

1 1
100

输出样例 3

0

---

输入样例 4

20 7
4262 9522 2426 3823 7364 964 2743 2423 1955 5274 3684 847 363 35 278 3220 203 2904 6304 1928

输出样例 4

22809