Takahashi tới một buổi tiệc với tư cách là vị khách đặc biệt. Có \(N\) vị khách bình thường khác nhau ở buổi tiệc, với vị khách thứ \(i\) có sức mạnh là \(A_i\).

Takahashi quyết định bắt tay \(M\) lần để tăng sự vui vẻ của buổi tiệc (cứ coi như bây giờ độ vui vẻ bằng \(0\)). Một lần bắt tay sẽ được thực hiện như sau:

• Takahashi chọn một vị khách \(x\) để bắt tay trái, và một vị khách \(y\) để bắt tay phải (\(x\) và \(y\) có thể giống nhau)
• Sau đó, anh ta bắt cả hai tay với hai vị khách \(x\) và \(y\) để tăng độ vui vẻ lên \(A_x + A_y\).

Tuy nhiên, Takahashi không thể thực hiện phép bắt tay giống hệt quá một lần. Cụ thể hơn, điều kiện sau cần được thỏa mãn:

• Giả sử ở lần bắt tay thứ \(k\), Takahashi bắt tay với vị khách \(x_k\) và \(y_k\). Khi đó, không tồn tại cặp \((p, q)\) \((1 \leq p < q \leq M\) sao cho \((x_p, y_p) = (x_q, y_q)\).

Hỏi, độ vui vẻ lớn nhất có thể đạt được sau \(M\) cú bắt tay là bao nhiêu?

Giới hạn

• \(1 \leq N \leq 10^5\)
• \(1 \leq M \leq N^2\)
• \(1 \leq A_i \leq 10^5\)
• Tất cả các giá trị đều là số nguyên.

Định dạng đầu vào

\(N\) \(M\)
\(A_1\) \(A_2\) \(\dots\) \(A_N\)

Định dạng đầu ra

In ra độ vui vẻ lớn nhất có thể đạt được sau \(M\) lần bắt tay

Ví dụ

5 3
10 14 19 34 33

202

9 14
1 3 5 110 24 21 34 5 3

1837

9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

8128170