Gift

Interview

Time limit1sMemory limit1024 MB

Summary

Given the daily sock prices, find the minimum cost to buy X socks on each of two consecutive days, 2X socks in total.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

Dongwon's birthday is $N$ days from now. Let's congratulate him!

Junwon plans to give Dongwon $2X$ socks as a birthday present. He will buy the socks at a market. Over two consecutive days, Junwon buys $X$ socks each day and loads them into a truck.

Sock prices at the market can differ from day to day. On the $i$ -th day counting from today, one sock costs $A_i$ won.

There are $N$ days left until Dongwon's birthday. Among those $N$ days, what is the minimum cost to buy $2X$ socks over two consecutive days?

Input

The first line contains $N$ and $X$ , separated by a space.

The second line contains the sock prices $A_1, A_2, \cdots, A_N$ for the $N$ days, separated by spaces.

Output

Print the minimum cost to buy $2X$ socks by buying $X$ socks per day over two consecutive days.

Constraints

$2 \le N \le 100\,000$
$1 \le X \le 1\,000\,000$
$1 \le A_i \le 1\,000$ ( $1 \le i \le N$ )

Examples2

Example 1
Input
```
5 10
9 2 5 7 6
```
Expected output
```
70
```
Example 2
Input
```
7 142857
22 35 9 12 25 19 10
```
Expected output
```
2999997
```