問題文

長さ N の正整数列 (A_1,A_2,\dots,A_N) が与えられます。 M=\max\,\{A_i\mid 1\leq i\leq N\} とし、区間 (0,M] を K 個の区間に分割します。すなわち、非負実数 m_i \, (i=0,1,\dots,K) を 0=m_0<m_1<m_2<\dots<m_{K-1}<m_K=M を満たすように選んで (0,M]=(m_0,m_1]\cup(m_1,m_2]\cup\dots\cup(m_{Kー1},m_{K}] とします。

区切り方を適切に定めたとき、 \[ \displaystyle \sum_{i=1}^{K} m_i \times (A_j \in (m_{i-1}, m_i]\text{となる}j\text{の個数}) \] の最小値を求めてください。答えは必ず整数になることが証明できます。

制約

• 1 \leq N \leq 10^5
• 1 \leq K \leq 10^5
• 1 \leq A_i \leq 10^5 \, (i=1,2,\dots,N)
• 入力はすべて整数

入力例 1

4 2
3 7 4 5

出力例 1

22

例えば、 (0,7]=(0,4]\cup(4,7] と分割すると、求める値は 4 \times 2 + 7 \times 2 = 22 となり、これが最小です。

入力例 2

19 4
3279 97197 36049 32099 29257 18290 96531 13435 88697 97081 71483 11396 77398 55303 4166 3906 12281 28658 30496

出力例 2

917886