配点 : 400 点
問題文
长度 小于或等于 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)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 \dots A_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