Điện toán đám mây

An là một lập trình viên điện toán đám mây. Hiện tại, anh ấy đang cần phải chạy tổng cộng $n$ chương trình mô phỏng trên "đám mây". Mỗi chương trình chạy mất đúng $1$ đơn vị thời gian, nhưng bộ nhớ chúng sử dụng có thể khác nhau. Bộ nhớ cần thiết cho chương trình $i$ là $a_i$ megabyte.

Theo công việc, An phải chia $n$ chương trình thành $k$ tác vụ và số chương trình trong mỗi tác vụ không nhất thiết bằng nhau. Mỗi chương trình thuộc đúng một tác vụ, mỗi tác vụ có ít nhất một chương trình, và các chương trình trong cùng một tác vụ không cần đứng liền nhau. Trong mỗi tác vụ, các chương trình được chạy lần lượt, tức là thời gian thực hiện một tác vụ sẽ bằng số chương trình trong tác vụ đó. Mặt khác, bộ nhớ được cấp phát cho mỗi tác vụ bằng bộ nhớ tối đa cần thiết cho bất kỳ một chương trình nào trong tác vụ đó.

Tuy nhiên, An phải trả chi phí cho mỗi megabyte trên một đơn vị thời gian, vì vậy chi phí cho mỗi tác vụ bằng số đơn vị thời gian thực hiện tác vụ đó nhân với bộ nhớ tối đa của các chương trình trong tác vụ và bằng số chương trình của tác vụ đó nhân với bộ nhớ tối đa của các chương trình trong tác vụ. Chi phí thực hiện $n$ chương trình sẽ là tổng chi phí thực hiện $k$ tác vụ.

Yêu cầu: Bạn hãy giúp An chia $n$ chương trình thành $k$ tác vụ, sao cho chi phí thực hiện chúng là tối thiểu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1\le k\le n\le {10}^5$).
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($0\le a_i\le {10}^{12}$).

Dữ liệu ra

In ra một số nguyên là chi phí tối thiểu mà An phải trả.

Ràng buộc

• $1\le k\le n\le {10}^5$.
• $0\le a_i\le {10}^{12}$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($4\%$ số test): $k=1$.
• Subtask 2 ($6\%$ số test): số các giá trị khác nhau của $a_1,a_2,\dots ,a_n$ nhỏ hơn hoặc bằng $k$.
• Subtask 3 ($10\%$ số test): $n\le 10$.
• Subtask 4 ($20\%$ số test): $n\le {10}^2$.
• Subtask 5 ($20\%$ số test): $n\le {10}^3$.
• Subtask 6 ($20\%$ số test): $n\le {10}^4$ và $k\le {10}^3$.
• Subtask 7 ($20\%$ số test): không có ràng buộc gì thêm.

Ví dụ