Quốc Dũng có một dãy \(a\) gồm \(n\) phần tử, các phần tử được đánh số từ 1 đến \(n\). Trong lớp của Quốc Dũng có Minh Hiếu và Phúc Hiếu là đôi bạn cùng lớp 10I. Minh Hiếu và Phúc Hiếu mỗi người chọn một chỉ số (hai chỉ số này không nhất thiết phải khác nhau), làm cho các phần tử có chỉ số nằm giữa hai chỉ số mà Minh Hiếu và Phúc Hiếu chọn (tính cả hai đầu mút) đều được nhân lên \(X\) lần.

Ví dụ dãy \(a = [5, 3, 7, 1]\), \(X = 2\): nếu Minh Hiếu chọn chỉ số 3, Phúc Hiếu chọn chỉ số 2 thì các phần tử ở chỉ số 2 và 3 được nhân đôi, dãy biến thành \([5, 6, 14, 1]\).

Yêu cầu

Hãy đưa ra tổng các phần tử của mảng nhỏ nhất có thể sau khi hai bạn chọn 2 chỉ số bất kì (không nhất thiết khác nhau) rồi thực hiện phép nhân lên mảng như trên.

Dữ liệu vào

Nhập từ bàn phím (standard input), gồm 2 dòng:

• Dòng 1: hai số nguyên \(n\) và \(X\) cách nhau bởi một khoảng trắng.
• Dòng 2: \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) cách nhau bởi khoảng trắng.

Dữ liệu ra

In ra màn hình (standard output) một số nguyên duy nhất là tổng nhỏ nhất có thể của mảng sau khi thực hiện phép nhân.

Ràng buộc

• \(1 \le n \le 10^6\).
• \(-10^9 \le a_i \le 10^9\).

• \(-1000 \le X \le 1000\).

• Subtask 1 (30% số test tương ứng 30% số điểm): \(n \le 10^2\).

• Subtask 2 (40% số test tương ứng 40% số điểm): \(n \le 10^3\).
• Subtask 3 (30% số test tương ứng 30% số điểm): \(n \le 10^6\).

Ví dụ

Input 1

4 2
5 3 7 1

17

Input 2

3 0
-1 -2 -3

-5