Contest Duration: - (local time) (100 minutes) Back to Home
G - Baseball /

Time Limit: 5 sec / Memory Limit: 1024 MB

### 問題文

まず、高橋君が、 1,2,\dots,N から K 個の相異なる整数 x_1,x_2,\dots,x_K を選びます。

### 制約

• 1 \leq N \leq 5 \times 10^4
• 1 \leq K \leq N
• 0 \leq P_i \leq 10^5
• 1 \leq \sum_{y'=1}^N P_{y'} \leq 10^5
• 入力はすべて整数

### 入力

N K
P_1 P_2 \dots P_N


### 入力例 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


Score : 650 points

### Problem Statement

You are given a sequence P=(P_1,P_2,\dots,P_N) of length N. Takahashi and Aoki will play a game using the sequence P.

First, Takahashi will choose K distinct integers x_1,x_2,\dots,x_K from 1,2,\dots,N.

Next, Aoki will choose an integer y from 1,2,\dots,N with a probability proportional to P_y. That is, the probability that integer y is chosen is \dfrac{P_y}{\sum_{y'=1}^N P_{y'}}. Then, Aoki's score will be \displaystyle \min_{i=1,2,\dots,K} |x_i-y|.

Takahashi wants to minimize the expected value of Aoki's score. Find the expected value of Aoki's score when Takahashi chooses x_1,x_2,\dots,x_K so that this value is minimized, multiplied by \sum_{y'=1}^N P_{y'}. It is guaranteed that the value to be printed is an integer.

### Constraints

• 1 \leq N \leq 5 \times 10^4
• 1 \leq K \leq N
• 0 \leq P_i \leq 10^5
• 1 \leq \sum_{y'=1}^N P_{y'} \leq 10^5
• All input values are integers.

### Input

The input is given from Standard Input in the following format:

N K
P_1 P_2 \dots P_N


### Sample Input 1

5 2
1 1 1 1 1


### Sample Output 1

3


The probabilities of Aoki choosing 1,2,\dots,N are all equal: \frac{1}{5}.

If Takahashi chooses x_1=2 and x_2=4, then the expected value of Aoki's score will be 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} = \frac{3}{5}.

If Takahashi chooses x_1=2 and x_2=3, then the expected value of Aoki's score will be 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 2 \times \frac{1}{5} = \frac{4}{5}.

No matter how Takahashi chooses, the expected value of Aoki's score cannot be smaller than \frac{3}{5}. Therefore, the minimum value is \frac{3}{5}, so print this value multiplied by 5, which is 3.

### Sample Input 2

5 1
0 0 1 0 0


### Sample Output 2

0


### Sample Input 3

1 1
100


### Sample Output 3

0


### Sample Input 4

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


### Sample Output 4

22809