棒球

题目描述

给定长度为 $N$ 的序列 $P=(P_1,P_2,\dots,P_N)$。高桥君和青木君将使用序列 $P$ 进行一个游戏。

首先，高桥君从 $1,2,\dots,N$ 中选择 $K$ 个不同的整数 $x_1,x_2,\dots,x_K$。

接下来，青木君从 $1,2,\dots,N$ 中选择一个整数 $y$，选择概率与 $P_y$ 成正比。即，整数 $y$ 被选中的概率为 $\dfrac{P_y}{\sum_{y'=1}^N P_{y'}}$。然后，青木君的得分为 $\displaystyle \min_{i=1,2,\dots,K} |x_i-y|$。

高桥君希望最小化青木君得分的期望值。求高桥君选择 $x_1,x_2,\dots,x_K$ 使该期望值最小时，青木君得分的期望值乘以 $\sum_{y'=1}^N P_{y'}$ 的结果。保证要输出的值是整数。

输入格式

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

$N$ $K$
$P_1$ $P_2$ $\dots$ $P_N$

输出格式

输出答案。

样例

5 2
1 1 1 1 1

3

5 1
0 0 1 0 0

0

1 1
100

0

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

22809

数据范围

• $1 \le N \le 5 \times 10^4$
• $1 \le K \le N$
• $0 \le P_i \le 10^5$
• $1 \le \sum_{y'=1}^N P_{y'} \le 10^5$
• 所有输入值均为整数